BZOJ 2190 欧拉函数

题

求(i,j)=1(i,j<n)的数的个数。

解

由原题显然可以得到上面的题意。
那么答案就是$ \sum_{i=2}^{n-1} \varphi(i) $。
注意(0,0),(0,1),(1,0)三组特殊点。
shacha的我连欧拉函数都不会求了。

码（3948 kb 24 ms）

#include <cstdio>
#include <cstring>
using namespace std;
template<class T> 
inline void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9'){if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
const int maxn = 4e5 + 100;
int phi[maxn] = {0};
int prime[maxn] = {0}, pcnt = 0;
int main()
{
    int n, ans; read(n);
    ans = n > 1 ? phi[1] = 1 : 0;
    for(int i = 2; i < n; i++)
    {
        if(!phi[i]) prime[pcnt++] = i, phi[i] = i - 1;
        for(int j = 0; j < pcnt && prime[j] * i < n; j++)
        {
            if(i % prime[j] == 0){phi[i * prime[j]] = phi[i] * prime[j]; break;}
            else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
        ans += phi[i];
    }
    printf("%d\n", ans * 2 + 1);
    return 0;
}