HDU 1286 找新朋友(歐拉函數)

題意  中文  就是求小于等于n的數中有多少個和n互質  即歐拉函數值

div[i] 表示i的最小質因數   eul[i]存儲i的歐拉函數值 

求歐拉函數的方法:

   1. eul[1]=1;

   2. 若i==p^k (p是素數)  eul[i]=(p-1)*p^(k-1);

   3. 若m,n互質, eul[m*n]=eul[m]*eul[n];

可以推出歐拉函數的遞推式

   若(i/div[i])%div[i]==0 則 eul[i]=eul[i/div[i]]*div[i] 否則  eul[i]=eul[i/div[i]]*(div[i] -1)

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 33000;
int div[N], eul[N];

void geneuller()
{
    for(int i = 1; i < N; ++i)   div[i] = i;
    for(int i = 2; i * i < N; ++i)
    {
        if(div[i] == i)
            for(int j = i * i; j < N; j += i) div[j] = i;
    }

    eul[1] = 1;
    for(int i = 2; i < N; ++i)
    {
        eul[i] = eul[i / div[i]];
        if((i / div[i]) % div[i] == 0) eul[i] *= div[i];
        else eul[i] *= div[i] - 1;
    }
}

int main()
{
    int cas, n;
    geneuller();
    scanf("%d", &cas);
    while(cas--)
    {
        scanf("%d", &n);
        printf("%d\n", eul[n]);
    }
    return 0;
}
           

找新朋友

Problem Description 新年快到了，“豬頭幫協會”準備搞一個聚會，已經知道現有會員N人，把會員從1到N編号，其中會長的号碼是N号，凡是和會長是老朋友的，那麼該會員的号碼肯定和N有大于1的公約數，否則都是新朋友，現在會長想知道究竟有幾個新朋友？請你程式設計式幫會長計算出來。  

Input 第一行是測試資料的組數CN（Case number，1<CN<10000），接着有CN行正整數N（1<n<32768），表示會員人數。  

Output 對于每一個N，輸出一行新朋友的人數，這樣共有CN行輸出。

Sample Input

2
25608
24027
        

Sample Output

7680
16016