HDU 6750 Function（莫比乌斯反演）（2020百度之星初赛1）

Function

推式子

$$\begin{gathered} S(n)=\sum _{i=1}^n\sum _{d\mid i}d[gcd(d,\frac{i}{d})==1] \\ =\sum _{d=1}^{n}d\sum _{d\mid i}[gcd(d,\frac{i}{d})==1] \\ =\sum _{d=1}^{n}d\sum _{i=1}^{\frac{n}{d}}[gcd(d,i)==1] \\ =\sum _{d=1}^{n}d\sum _{i=1}^{\frac{n}{d}}\sum _{k\mid gcd(d,i)}\mu (k) \\ =\sum _{k=1}^n\mu (k)k\sum _{d=1}^{\frac{n}{k}}d\sum _{i=1}^{\frac{n}{k^{2}d}} \\ t=k^{2}d \\ =\sum _{t=1}^n\frac{n}{t}\sum _{k^2\mid t}\mu (k)k\frac{t}{k^2} \\ =\sum _{k=1}^{\sqrt{n}}\mu (k)k\sum _{k^2\mid t}\frac{n}{t}\frac{t}{k^2} \\ i=\frac{t}{k^2} \\ =\sum _{k=1}^{\sqrt{n}}\mu (k)k\sum _{i=1}^{\frac{n}{k^2}}\frac{n}{i{k}^2}i \end{gathered}$$

​

代码

注意随手取模，long long $\times$long long会溢出！！！

/* Author : lifehappy */ #pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const double eps = 1e-7; const int N = 1e6 + 10, mod = 1e9 + 7, inv2 = mod + 1 >> 1; int prime[N], cnt; ll mu[N]; bool st[N]; void init() { mu[1] = 1; for(int i = 2; i < N; i++) { if(!st[i]) { prime[cnt++] = i; mu[i] = -1; } for(int j = 0; j < cnt && i * prime[j] < N; j++) { st[i * prime[j]] = 1; if(i % prime[j] == 0) break; mu[i * prime[j]] = -mu[i]; } } for(int i = 1; i < N; i++) { mu[i] = (mu[i - 1] + 1ll * i * mu[i] % mod + mod) % mod; } } ll calc1(ll l, ll r) { return 1ll * (l + r) % mod * ((r - l + 1) % mod) % mod * inv2 % mod; } ll calc2(ll n) { ll ans = 0; for(ll l = 1, r; l <= n; l = r + 1) { r = n / (n / l); ans = (ans + 1ll * (n / l) % mod * calc1(l, r) % mod) % mod; } return ans; } int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); init(); int T; scanf("%d", &T); while(T--) { ll n, ans = 0; scanf("%lld", &n); int m = sqrt(n); for(ll l = 1, r; l <= m; l = r + 1) { r = min((int)sqrt(n / (n / (l * l))), m); ans = (ans + 1ll * ((mu[r] - mu[l - 1]) % mod + mod) % mod * calc2(n / (l * l)) % mod) % mod; } printf("%lld\n", ans); } return 0; }