∑lcm(i,n) = ∑ i*n/(i,n) = ∑d|n∑(x,n)=d x*n/d = ∑d|n∑(t,n/d)=1t*n = n∑d|nf(d). f(d)表示1~d中与d互质的数的和, 即f(d) = d*φ(d)/2(d>=2). 然后O(n)筛φ, 每次询问暴力算即可...最大是100w,sqrt(100w)=1000内的质数是168个, 所以复杂度是O(n + T*168), 可以AC
----------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000009;
bool check[maxn];
int prime[maxn], pn = 0, phi[maxn];
ll f[maxn];
void init() {
memset(check, 0, sizeof check);
for(int i = 2; i < maxn; i++) {
if(!check[i]) {
prime[pn++] = i;
f[i] = ll(i) * (phi[i] = i - 1) >> 1;
}
for(int j = 0; j < pn && i * prime[j] < maxn; j++) {
check[i * prime[j]] = 1;
if(i % prime[j]) {
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
f[i * prime[j]] = ll(i) * prime[j] * phi[i * prime[j]] >> 1;
} else {
phi[i * prime[j]] = phi[i] * prime[j];
f[i * prime[j]] = ll(i) * prime[j] * phi[i * prime[j]] >> 1;
break;
}
}
}
}
void work(int n) {
if(n == 1) {
puts("1");
return;
} else if(n == 2) {
puts("4");
return;
} else if(n == 3) {
puts("12");
return;
}
ll ans = 0;
int m = (int)sqrt(n + 0.1);
for(int i = 1; i * i < n; i++) if(n % i == 0)
ans += f[i] + f[n / i];
if(m * m == n) ans += f[m];
printf("%lld\n", ans * n);
}
int main() {
init(); f[1] = 1;
int T; scanf("%d", &T);
while(T--) {
int n; scanf("%d", &n);
work(n);
}
return 0;
}
-----------------------------------------------------------------------------------
2226: [Spoj 5971] LCMSum
Time Limit: 20 Sec Memory Limit: 259 MB
Submit: 886 Solved: 404
[Submit][Status][Discuss]Description
Given n, calculate the sum LCM(1,n) + LCM(2,n) + .. + LCM(n,n), where LCM(i,n) denotes the Least Common Multiple of the integers i and n.
Input
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output
Output T lines, one for each test case, containing the required sum.
Sample Input
3
1
2
5
Sample Output
1
4
55
HINT
Constraints
1 <= T <= 300000
1 <= n <= 1000000
Source
BZOJ 2226: [Spoj 5971] LCMSum( 数论 )
原文：http://www.cnblogs.com/JSZX11556/p/4776717.html
