[欧拉函数] uva 11426 GCD - Extreme (II)

题意：

求1~n之间两两gcd的和，gcd(a,b)和gcd(b,a)算一个。

思路：

设gcd(x,n)=i的x的个数为g(n,i)，则g(n,i)=phi(n/i)。phi(x)为x的欧拉函数值。
注：这里x<n。

所以采用打表的方法

ans[i]=ans[i-1]+g[i]

g[i]为1~i之间的数与i的gcd之和。

而求g[i]的方法就需要用筛选法了

代码：

#include"cstdio"
#include"cstring"
#include"cmath"
#include"cstdlib"
#include"algorithm"
#include"iostream"
#include"map"
#include"queue"
#define ll long long
using namespace std;
#define MAX 4000007
int phi[MAX];
int g[MAX+10];
ll ans[MAX+10];
void Eorue()
{
    phi[1]=1;
    int i,j ;
    for(i=2; i<MAX; i++)
    {
        if(!phi[i])
        {
            for(j=i; j<MAX; j+=i)
            {
                if(!phi[j])
                    phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}
int main()
{
    Eorue();
    for(int i=1; i<MAX; i++)
    {
        for(int j=i+i; j<MAX; j+=i)
            g[j]+=i*phi[j/i];
    }
    ans[2]=g[2];
    for(int i=3;i<MAX;i++) ans[i]=ans[i-1]+g[i];
    int n;
    while(scanf("%d",&n),n)
    {
        printf("%lld\n",ans[n]);
    }
    return 0;
}

[欧拉函数] uva 11426 GCD - Extreme (II)

原文：http://blog.csdn.net/wdcjdtc/article/details/44654241