[欧拉函数] uva 11426 GCD

题意：

求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 longusing namespace std;#define MAX 4000007int 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;}

旅行要学会随遇而安，淡然一点，