新しい友達を探す|HDU 1286

タイトルリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1286 Problem Descriptionの新年はもうすぐです.「豚頭帮协会」はパーティーをするつもりです.既存の会員N人が、会員を1からN番号にしていることを知っています.その中の会長の番号はN番です.会長と古い友达であれば、その会員の番号はNと1より大きい公約数があるに違いありません.そうしないと、新しい友达になります.今会長はいったい何人の新しい友达がいるのか知りたいと思っています.プログラムを作って会長の計算を手伝ってください.
Input

           CN（Case number，（1~10000）），   CN    N（1~32768），      。

Output

     N，          ，    CN   。

Sample Input

2
25608
24027

Sample Output

7680
16016

問題解:簡単なオーラ関数の応用ここにオーラ関数の説明があります.http://blog.csdn.net/csdn_muxin/article/details/76374939

#include
#include
#include
#include
#include
#include
using namespace std;
int eular(int n)
{
    int i,r=1;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n=n/i;
            r*=(i-1);
            while(n%i==0)
            {
                n=n/i;
                r*=i;
            }
        }
    }
    if(n>1)
      r*=(n-1);
return r;
}
int main()
{
    int t,n,s;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        s=eular(n);
        printf("%d
",s);
    }
return 0;
}