题目链接：uva 11426 - GCD - Extreme

题目大意：给出n，求∑i!=jngcd(i,j)

解题思路：f(n)=gcd(1,n)+gcd(2,n)+?+gcd(n?1,n)
S(n)=f(2)+f(3)+?+f(n)
S(n)=S(n?1)+f(n)
问题转化成怎么求f(n),对于一个n来说，枚举因子乘上个数即可。

#include 
   
     #include 
    
      const int N = 4000000; typedef long long ll; int phi[N+5]; ll s[N+5], f[N+5]; void phi_table(int n) { for (int i = 2; i <= n; i++) phi[i] = 0; phi[1] = 1; for (int i = 2; i <= n; i++) { if (!phi[i]) { for (int j = i; j <= n; j += i) { if (!phi[j]) phi[j] = j; phi[j] = phi[j] / i * (i-1); } } } } int main () { phi_table(N); memset(f, 0, sizeof(f)); for (int i = 1; i <= N; i++) { for (int j = i * 2; j <= N; j += i) { f[j] += i * phi[j/i]; } } s[2] = f[2]; for (int i = 3; i <= N; i++) s[i] = s[i-1] + f[i]; int n; while (scanf("%d", &n) == 1 && n) { printf("%lld\n", s[n]); } return 0; }