uva-11426-数论

https://vjudge.net/problem/UVA-11426#author=0

求 SUM{ gcd(i,j) | 1<=i<j<=n}, n<4000001。

令f(n)=gcd(1,n)+gcd(2,n)+...+gcd(n-1,n),

则 S(n)=f(2)+f(3)+...+f(n) 即为我们所求答案，问题转化为求解f(n)。

　　可以看出对于f(n)的所有项的答案一定是n的因子，我们不妨令g(x,i)表示因子i对应的f(n)里的项x的个数，

那么f(n)=SUM{ i*g(x,i) | i为n的因子且0<x<n}  有gcd(x,n)==i  -->  gcd(x/i,n/i)==1 ,所以因子i对应的x的个数就

等价于与n/i互质且小于n/i的数的个数，这个就可以用phi来求解了。

 　　在求f的时，一开始是用的O(N*sqrt(N))来一个一个找会T，太蠢了。只要和打表phi一样利用类似于埃筛

的方法就可以降到O(N*log(N))了。

　　

#include<bits/stdc++.h>
using namespace std;
#define LL long long 
const int maxn=4000001;
LL f[maxn];
int phi[maxn];
void init(){
    phi[1]=1;
    int m=sqrt(maxn+0.5);
    for(int i=2;i<maxn;++i){
        if(!phi[i]){
            for(int j=i;j<maxn;j+=i){
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
    for(int i=1;i<maxn;++i){
        for(int j=i*2;j<maxn;j+=i){
            f[j]+=i*phi[j/i];
        }
    }
    for(int i=3;i<maxn;++i) f[i]+=f[i-1];
}
int main(){
    init();
    int n;
    while(scanf("%d",&n)&&n){
        printf("%lld
",f[n]);
    }
    return 0;
}