【题解】POJ P3090 【Visible Lattice Points】

这题就是求多少个$x(1\leq x < y)$且$gcd(x,y)==1$,这里有莫比乌斯反演的解法。当然也可用欧拉函数解。

显然本题答案就是$3 + 2\times \sum_{i=2}^{N}phi(i)$,然后筛一遍欧拉函数就好了。

#include<cstdio>
#include<algorithm>

namespace OI{
    using std::fill;
}
using namespace OI;

const int MAXN = 1000 + 6;
int primes[MAXN],mu[MAXN],phi[MAXN],num;
bool isPrime[MAXN];

void sieve(){
    fill(isPrime,isPrime + MAXN,true);
    mu[1] = 1;
    phi[1] = 1;
    num = 0;
    for(int i = 2;i < MAXN;++i){
        if(isPrime[i]){
            primes[num++] = i;
            mu[i] = -1;
            phi[i] = 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){
                phi[d] = primes[j] * phi[i];
                mu[d] = 0;
                break;
            }else{
                phi[d] = (primes[j] - 1) * phi[i];
                mu[d] = -mu[i];
            }
        }
    }
}

int main(){
    sieve();
    
    int T;
    scanf("%d",&T);
    
    int Case = 1;
    while(T--){
        int n;
        scanf("%d",&n);
        
        int ans = 0;
        for(int i = 2;i <= n;i++){
            ans += phi[i];
        }
        ans *= 2;
        ans += 3;
        printf("%d %d %d\n",Case,n,ans);
        Case++;
    }
    
    return 0;
}