POJ 2407 Relatives

欧拉函数的应用，素数定理；

看了DISCUSS中那段超短的代码后才明白欧拉函数直接解决，我之前想的是集合中的容斥定理，实际上这里欧拉公式也实质上就是容斥定理；

另外用了刚学的优化的筛法计算素数表。

# include <stdio.h>

# define N 1000005

int m;
char pt[N];
int p[N/10];

void build_ptable(void);
int solve(int n);

int main()
{
    int n;
    
    build_ptable();
    while (~scanf("%d", &n) && n)
        printf("%d\n", solve(n));
    
    return 0;
}

void build_ptable(void)
{
    int i, j, k;
    
    m = 0;
    for (i = 2; i < N; ++i)
    {
        if (!pt[i]) p[m++] = i;
        for (j = 0; j<m && i*p[j]<=N; ++j)
        {
            pt[i*p[j]] = 1;
            if (i%p[j] == 0) break;    
        }
    }
}

int solve(int n)
{
    int i, ret;
    
    ret = n;
    for (i = 0; i<m && n>1; ++i)
        if (n%p[i] == 0) 
        {
            ret = ret - ret/p[i];
            while (n%p[i] == 0) n /= p[i];
        }
    if (ret == n) return (n==1 ? 0:n-1);    
    
    return ret;
}