绝世【】题

· · 算法·理论

（这文章太神秘被投休闲娱乐了）

神秘 jsy 题单的神秘投稿

原题目描述：

你这家伙在说什么呢

化简

令 S = \{d,r,e,a,m\}，那么分子为

G_1=\prod_{T\subset S,|T|=3}\gcd(T)

分母前一段为

G_2^3,G_2=\gcd(\{x|x=\operatorname{lcm}(T),T\subset S,|T|=2\})

后面是

G_3=\gcd(\{x|x=\operatorname{lcm}(T),T\subset S,|T|=3\})

用 v_p(x) 表示 p 这个质数在 x 中的指数，那么根据

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))

对于某一质数 p，简写 v_x=v_p(x)，则在 G_1 中的指数就是

g_1=\sum_{T\subset S,|T|=3}\min\{v_x:x\in T\}

在 G_2 中就是

g_2=\min_{\{i,j\}\subset S}\max(v_i,v_j)

在 G_3 中就是

g_3=\min_{T\subset S,|T|=3}\max\{v_x:x\in T\}

于是原分数对 p 的指数就是

A=g_1-3g_2-g_3

对 v_d,v_r,v_e,v_a,v_m 进行排序，得到 a_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) 是 g(x) 的狄利克雷逆，即 g(x)=\sum_{d|x}f(d)，由于 g(x)=x^6，那么 f(x)=\sum_{d|x}\mu(d)(\frac{x}{d})^6，发现 f(x) 可以线性筛

交换一下求和顺序

原式=\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

#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))}