【题解】UVa P10820【Send a Table】

背景

这题好经典的

分析

题所求即$\sum_{i=1}^{n}\sum_{j=1}^{n}\gcd(i,j)==1$的个数,这样既可以用欧拉函数,当然也可以莫比乌斯反演。
关于反演:点我点我
然后我们只需要筛出莫比乌斯函数,然后套反演应用就好了,代码短,速度快,0ms暴虐数据。

代码

#include<cstdio>
#include<algorithm>
using std::fill;
const int MAXN = 50000 + 6;
int primes[MAXN],mu[MAXN],num;
bool isPrime[MAXN];

void sieve(){
    fill(isPrime,isPrime + MAXN,true);
    mu[1] = 1,num = 0;
    for(int i = 2;i < MAXN;++i){
        if(isPrime[i]) primes[num++] = i,mu[i] = -1;
        static int d;
        for(int j = 0;j < num && (d = i * primes[j]) < MAXN;++j){
            isPrime[d] = false;
            if(i % primes[j] == 0){
                mu[d] = 0;break;
            }else mu[d] = -mu[i];
        }
    }
}

int main(){
    sieve();
    int n,ans;
    while(scanf("%d",&n) == 1 && n){
        ans = 0;
        for(int x = 1;x <= n;x++) ans += (mu[x] * (n / (1 * x)) * (n / (1 * x)));
        printf("%d\n",ans);
    }

    return 0;
}