题意： 求 n 以内gcd( i , j ) i < j 的和的个数。
n 的欧拉函数值 表示 小于 n 与 n 互质的数的个数。
对于互质的两个数 a,b (a<b<=n), gcd（a,b） = 1 是显然的。
对 b 而言互质的数有 fai(b) = m个 ，那么b 的贡献就是 m。如果是 2*b呢？ 那贡献就是2*m
因为将与 b 互质的m个数都乘2， 就得到 m 个 gcd(2*a,2*b) = 2的数
但2*b不仅仅有 2*m个，因为它也可以通过别的数相乘得到 。那么只需要求出每个数的欧拉函数，
再对 i * j 下标累加 j * fai(i) 个贡献就行，j从1倍一直到小于maxn。
求出的是 i 以内的gcd()和，前 i 项gcd() 和累加就行。
代码语言：javascript复制//uva 11426 欧拉函数的运用
#include <iostream>
#include <algorithm>
#include <cstring>
#define ll long long
using namespace std;
const int maxn = 4000051;
bool is_prime[maxn];
int prime[maxn],phi[maxn];
ll a[maxn];
void getphi(){
memset(is_prime,0,sizeof(is_prime));
phi[1] = 1;
for(int i=2;i<maxn;i ){
if(!is_prime[i]){
prime[ prime[0]] = i;
phi[i] = i-1;
}
for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j ){
is_prime[prime[j]*i] = 1;
if(i%prime[j]==0){
phi[i*prime[j]] = phi[i]*prime[j];
}else{
phi[i*prime[j]] = phi[i]*(prime[j]-1);
}
}
}
}
void solve(){
getphi();
for(int i=2;i<maxn;i ){
for(int j=1;j*i<maxn;j ){
a[j*i] =j*phi[i];
}
}
for(int i=1;i<maxn;i )
a[i] =a[i-1];
}
int main() {
solve();
int n;
while(scanf("%d",&n)&&n){
printf("%lldn",a[n]);
}
return 0;
}
