SPOJ 3871 GCD Extreme

タイトルリンク:http://www.spoj.com/problems/GCDEX/
タイトル:

考え方:

 

int phi[N];

i64 f[N];



void init()

{

    phi[1]=1;

    int i,j;

    for(i=2;i<N;i++) if(!phi[i]) for(j=i;j<N;j+=i)

    {

        if(!phi[j]) phi[j]=j;

        phi[j]-=phi[j]/i;

    }

    for(i=2;i<N;i++) f[i]=phi[i];

    for(i=2;i*i<N;i++)

    {

        f[i*i]+=(i64)phi[i]*i;

        for(j=i+1;j*i<N;j++) f[i*j]+=(i64)phi[i]*j+(i64)phi[j]*i;

    }

    for(i=2;i<N;i++) f[i]+=f[i-1];

}



int n;



int main()

{

    init();

    Rush(n)

    {

        if(n==0) break;

        printf("%lld
",f[n]);

    }

}