Description
HDU5382
会吗？不会！
设(F(n)=sumlimits_{i = 1}^{n}sumlimits_{j=1}^{n}[lcm(i,j)+gcd(i,j)ge n])，求(S(n)=sumlimits_{i=1}^{n}F(n))
Soluiton
[F(n) = n^2 - sumlimits_{i = 1}^{n}sumlimits_{j=1}^{n}[lcm(i,j)+gcd(i,j) < n]\
F(n) - F(n-1) = n^2 - sumlimits_{i = 1}^{n}sumlimits_{j=1}^{n}[lcm(i,j)+gcd(i,j) < n] - (n-1)^2 - sumlimits_{i = 1}^{n-1}sumlimits_{j=1}^{n-1}[lcm(i,j)+gcd(i,j) < n-1]\
= 2n - 1 - sumlimits_{i = 1}^{n}sumlimits_{j=1}^{n}[lcm(i,j)+gcd(i,j) = n]\
F(n) = F(n-1) + (2n-1) - sumlimits_{i = 1}^{n}sumlimits_{j=1}^{n}[lcm(i,j)+gcd(i,j) = n]
]
设
[G(n) = sumlimits_{i = 1}^{n}sumlimits_{j=1}^{n}[lcm(i,j)+gcd(i,j) = n]\
= sumlimits_{i = 1}^{n}sumlimits_{j=1}^{n}[dfrac{k_igcd(i,j)cdot k_j gcd(i,j)}{gcd(i,j)}+gcd(i,j) = n]\
= sumlimits_{d=1}^{n}sumlimits_{i=1}^{lfloor dfrac{n}{d}
floor}sumlimits_{j=1}^{lfloor dfrac{n}{d}
floor}[ijd + d = n][gcd(i,j) = 1]\
= sumlimits_{d|n}sumlimits_{i=1}^{dfrac{n}{d}}sumlimits_{j=1}^{dfrac{n}{d}}[(ij) = dfrac{n}{d} - 1][gcd(i,j) = 1]\
]
设
[H(n) = sumlimits_{i=1}^{n+1}sumlimits_{j=1}^{n+1}[ij = n][gcd(i,j) = 1]\
= sumlimits_{i=1} [gcd(i, dfrac{n}{i}) = 1]
]
则
[G(n) = sumlimits_{d|n} H(dfrac{n}{d} - 1)
]
不难想到，将(n)质因数分解后，(p_x^{a_x})要么在(i)那一部分，要么在(dfrac{n}{i})那一部分，所以
[H(n) = 2^k (k mbox{ is the number of prime factors of }n)
]
所以(H(n)) 是一个积性函数，可以欧拉筛。然后在计算每个(H)对(G)的贡献，这样复杂度是(O(nlogn))的，然后就能(O(n))的求出(F)和(S)。
综上，这个题不涉及NOIp以外的知识，NOIp可以考这么难的
Code
#include <bits/stdc++.h>
typedef long long LL;
const int N = 1e6 + 10;
const LL MOD = 258280327;
LL F[N], G[N], H[N], S[N];
int notp[N], pri[N], cnt;
int get_prime() {
for (int i = 1; i < N; ++i) H[i] = 1;
for (int i = 2; i < N; ++i) {
if (!notp[i]) {
pri[cnt++] = i;
H[i] = 2;
}
for (int j = 0; j < cnt; ++j) {
int k = i * pri[j];
if (k >= N) break;
notp[k] = 1;
if (i % pri[j] == 0) {
(H[k] *= H[i]) %= MOD;
break;
}
else {
(H[k] *= 2 * H[i] % MOD) %= MOD;
}
}
}
for (int i = 1; i < N; ++i) {
for (int j = i; j < N; j += i) {
G[j] = (G[j] + H[j/i - 1]) % MOD;
}
}
F[1] = 1;
for (int i = 2; i < N; ++i) {
F[i] = ((LL)F[i-1] + i + i - 1LL - G[i-1]) % MOD;
}
for (int i = 1; i < N; ++i) {
S[i] = (S[i-1] + F[i]) % MOD;
}
}
int main() {
get_prime();
int t;
scanf("%d", &t);
while (t--) {
int n;
scanf("%d", &n);
printf("%d
", S[n]);
}
return 0;
}