hdu 1286

地址：http://acm.hdu.edu.cn/showproblem.php?pid=1286

题意：中文。

mark：看似很绕其实就是求欧拉函数Phi(n)。

对于所有n的素因子Pi，欧拉函数Phi(n) = n * (P1-1)/P1 * (P2-1)/P2 * (P3-1)/P3 ...。

对于每一个Pi，因为n总是Pi的倍数，所以可以先除再乘，不会溢出。

代码：

# include <stdio.h>


int Primes[40000] = {2, 3} ;
int PrimeNum = 2 ;
int dp[40000] ;


int calc(int nn)
{
    int ans = nn, j = 0 ;
    while (nn != 1)
    {
        if (nn % Primes[j] == 0)
        {
            ans /= Primes[j] ; 
            ans *= (Primes[j]-1) ;
            while(nn % Primes[j] == 0) nn/=Primes[j] ;
        }
        j++ ;
    }
    return ans ;
}

void init ()
{
    int i, j ;
    for (i = 5 ; i <= 32768 ; i+=2)
    {
        for (j = 0 ; j < PrimeNum ; j++)
            if (i % Primes[j] == 0) break ;
        if (j >= PrimeNum)
            Primes[PrimeNum++] = i ;
    }
    for (i = 2 ; i < 32768 ; i++)
        dp[i] = calc(i) ;
}


int main ()
{
    int T, n ;
    init () ;
    scanf ("%d", &T) ;
    while (T--)
    {
        scanf ("%d", &n) ;
        printf ("%d\n", dp[n]) ;
    }
    return 0 ;
}