Given the value of N, you will have to find the value of G. The meaning of G is given in the following code
G=0; 
for(i=1;i<N;i++)   
    for(j=i+1;j<=N;j++) 
      G+=gcd(i,j);

#include<iostream>
#include<cstdio>

using namespace std;
#define maxn 1000005
#define LL __int64

int phi[maxn];
LL ans[maxn];

void Init()
{
    int i,j,k;
    for(i=2;i<maxn;i++) phi[i]=i;
    for(i=2;i<maxn;i++)
        if(phi[i]==i)
            for(j=i;j<maxn;j+=i)
                phi[j]=phi[j]/i*(i-1);
    for(i=2;i<maxn;i++)
        ans[i]=phi[i];
    for(i=2;i<=1000;i++)
    {
        ans[i*i]+=phi[i]*i;
        for(j=i*i+i,k=i+1;j<maxn;j+=i,k++)
            ans[j]+=i*phi[k]+k*phi[i]; 
    }
    for(i=1;i<maxn;i++)
        ans[i]+=ans[i-1];
}

int main()
{
    Init();
    int n;
    while(scanf("%d",&n),n)
        printf("%I64d\n",ans[n]);
    return 0;
}
0
Posted in ACM

Leave a Comment:

电子邮件地址不会被公开。