【spoj 】LCMSUM
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.
The first line contains T the number of test cases. Each of the next T lines contain an integer n.
Output T lines, one for each test case, containing the required sum.
Sample Input: 3 1 2 5 Sample Output: 1 4 55
1 <= T <= 300000
1 <= n <= 1000000
#include<cstdio> #include<iostream> #define ll long long using namespace std; const int MAXN = 1000010; int phi[MAXN], pri[MAXN]; ll ans[MAXN]; bool vis[MAXN]; void init() { phi[1] = 1; int cnt = 0; for (int i = 2; i < MAXN; i++) { if (!vis[i]) pri[++cnt] = i, phi[i] = i - 1,vis[i] = 1; for (int j = 1; j <= cnt && i*pri[j] < MAXN; j++) { vis[i*pri[j]] = 1; if (i%pri[j] == 0) { phi[i*pri[j]] = phi[i] * pri[j]; break; } phi[i*pri[j]] = phi[i] * (pri[j] - 1); } }for (int i = 1; i < MAXN; i++) for (int j = 1; i*j < MAXN; j++) ans[i*j] += 1LL * j*phi[j]/2; for (int i = 1; i < MAXN; i++) ans[i] = i * ans[i] + i; } int main() { int T; init(); scanf("%d", &T); while (T--) { int n; scanf("%d", &n); printf("%lld\n", ans[n]); } return 0; }
原文：https://www.cnblogs.com/rentu/p/11256309.html
