专栏文章

绝世【】题

DDJ_Liu
算法·理论参与者 81已保存评论 90

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
90 条
当前快照
1 份
快照标识符
@mlgxtgzg
此快照首次捕获于
2026/02/11 02:31
上周
此快照最后确认于
2026/02/19 01:13
11 小时前
查看原文
（这文章太神秘被投休闲娱乐了）
神秘 jsy 题单的神秘投稿
原题目描述：
你这家伙在说什么呢

化简

令 S={d,r,e,a,m}S = \{d,r,e,a,m\}，那么分子为 G1=∏T⊂S,∣T∣=3gcd⁡(T)G_1=\prod_{T\subset S,|T|=3}\gcd(T) 分母前一段为 G23,G2=gcd⁡({x∣x=lcm⁡(T),T⊂S,∣T∣=2})G_2^3,G_2=\gcd(\{x|x=\operatorname{lcm}(T),T\subset S,|T|=2\}) 后面是 G3=gcd⁡({x∣x=lcm⁡(T),T⊂S,∣T∣=3})G_3=\gcd(\{x|x=\operatorname{lcm}(T),T\subset S,|T|=3\})
用 vp(x)v_p(x) 表示 pp 这个质数在 xx 中的指数，那么根据 vp(gcd⁡(x,y))=min⁡(vp(x),vp(y)),vp(lcm⁡(x,y))=max⁡(vp(x),vp(y))v_p(\gcd(x,y))=\min(v_p(x),v_p(y)),v_p(\operatorname{lcm}(x,y))=\max(v_p(x),v_p(y)) 对于某一质数 pp，简写 vx=vp(x)v_x=v_p(x)，则在 G1G_1 中的指数就是 g1=∑T⊂S,∣T∣=3min⁡{vx:x∈T}g_1=\sum_{T\subset S,|T|=3}\min\{v_x:x\in T\} 在 G2G_2 中就是 g2=min⁡{i,j}⊂Smax⁡(vi,vj)g_2=\min_{\{i,j\}\subset S}\max(v_i,v_j) 在 G3G_3 中就是 g3=min⁡T⊂S,∣T∣=3max⁡{vx:x∈T}g_3=\min_{T\subset S,|T|=3}\max\{v_x:x\in T\} 于是原分数对 pp 的指数就是 A=g1−3g2−g3A=g_1-3g_2-g_3 对 vd,vr,ve,va,vmv_d,v_r,v_e,v_a,v_m 进行排序，得到 a1≤a2≤a3≤a4≤a5a_1\le a_2\le a_3\le a_4\le a_5，则
g_1 & = & 6a_1+3a_2+a_3 \\ g_2 & = & a_2 \\ g_3 & = & a_3 \end{array}$$ 于是 $$A=g_1-3g_2-g_3=6a_1$$ 对于每个质数 $p$，原分数中 $p$ 的指数都是 $\min{v_p(x)}$，于是原分数就是 $$\prod_{p\in P}p^{6\min\{v_p(x),x\in S\}}=\gcd(S)^6$$ wow 好好看 # 算 正戏开始，令 $g(x)=x^6$
\begin{aligned} 原式 & =\sum_{d=1}^D\sum_{r=1}^R\sum_{e=1}^E\sum_{a=1}^A\sum_{m=1}^M\gcd(d,r,e,a,m)^6 \ & = \sum_{d=1}^D\sum_{r=1}^R\sum_{e=1}^E\sum_{a=1}^A\sum_{m=1}^Mg(\gcd(d,r,e,a,m)) \ & = \sum_{d=1}^D\sum_{r=1}^R\sum_{e=1}^E\sum_{a=1}^A\sum_{m=1}^M\sum_{x|\gcd(d,r,e,a,m)}f(x) \ \end{aligned}$$ 这里 f(x)f(x) 是 g(x)g(x) 的狄利克雷逆，即 g(x)=∑d∣xf(d)g(x)=\sum_{d|x}f(d)，由于 g(x)=x6g(x)=x^6，那么 f(x)=∑d∣xμ(d)(xd)6f(x)=\sum_{d|x}\mu(d)(\frac{x}{d})^6，发现 f(x)f(x) 可以线性筛
交换一下求和顺序 原式=∑x=1min⁡(D,R,E,A,M)f(x)⌊Dx⌋⌊Rx⌋⌊Ex⌋⌊Ax⌋⌊Mx⌋原式=\sum_{x=1}^{\min(D,R,E,A,M)}f(x)\left\lfloor\frac{D}{x}\right\rfloor\left\lfloor\frac{R}{x}\right\rfloor\left\lfloor\frac{E}{x}\right\rfloor\left\lfloor\frac{A}{x}\right\rfloor\left\lfloor\frac{M}{x}\right\rfloor 看起来人畜无害多了，是五个整除分块，于是就能写了

代码

卡常卡一晚上没卡过，干脆不卡了，如果你想你可以试试，下面的代码只能过43pts
CPP
#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define endl '\n'
using namespace std; 
#define ll long long

const int maxn = 5e7 + 10, mod = 1e9 + 7; 
int pr[maxn], ntp[maxn], f[maxn], cnt;
int get(int x) {
    x = (ll)x * x % mod;
    return (ll)x * x % mod * x % mod;
}
void init() {
    f[1] = 1;
    for (ll i = 2; i < maxn; i++) {
        if (!ntp[i]) pr[++cnt] = i, f[i] = get(i) - 1;
        for (int j = 1; j <= cnt && i * pr[j] < maxn; j++) {
            ntp[i * pr[j]] = 1;
            f[i * pr[j]] = (ll)f[i] * get(pr[j]) % mod;
            if (i % pr[j] == 0) break;
            if ((f[i * pr[j]] -= f[i]) < 0) f[i * pr[j]] += mod;
        }
    }
    for (int i = 1; i < maxn; i++) if ((f[i] += f[i - 1]) >= mod) f[i] -= mod;
}
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    init();
    int t;
    cin >> t;
    while (t--) {
        ll d, r, e, a, m;
        cin >> d >> r >> e >> a >> m;
        ll ans = 0;
        for (ll l = 1, _r; l <= min({d, r, e, a, m}); l = _r + 1) {
            _r = min({d / (d / l), r / (r / l), e / (e / l), a / (a / l), m / (m / l)});
            (ans += (ll)(f[_r] - f[l - 1] + mod) * (d / l) % mod * (r / l) % mod * (e / l) % mod * (a / l) % mod * (m / l) % mod) %= mod;
        }
        cout << ans << endl;
    }
    return 0; 
}
啊啊啊宝宝你是一个
\operatorname{lcm}(r,e),\operatorname{lcm}(r,a),\operatorname{lcm}(r,m),\operatorname{lcm}(e,a),\operatorname{lcm}(e,m),\operatorname{lcm}(a,m))^3\gcd(\operatorname{lcm}(d,r,e),\operatorname{lcm}(d,r,a),\operatorname{lcm}(d,r,m), \operatorname{lcm}(d,e,a),\operatorname{lcm}(d,e,m),\operatorname{lcm}(d,a,m),\operatorname{lcm}(r,e,a),\operatorname{lcm}(r,e,m),\operatorname{lcm}(r,a,m),\operatorname{lcm}(e,a,m))}$$

评论

共 90 条评论，欢迎与作者交流。

正在加载评论...