题目大意:

新年快到了,“猪头帮协会”准备搞一个聚会,已经知道现有会员N人,把会员从1到N编号,其中会长的号码是N号,凡是和会长是老朋友的,那么该会员的号码肯定和N有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。


解题思路:这是一道裸的欧拉函数题目
        对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler's totient function、φ函数、欧拉商数等。
       

 

Euler函数

       欧拉函数通式:φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数,x是不为0的整数。φ(1)=1      (唯 一和1互质的数就是1本身)。 
       
      
代码:

 1#include <iostream>
 2#include <cstdio>
 3#include <cmath>
 4#include <cstring>
 5
 6using namespace std;
 7
 8int n,T;
 9
10int euler(int x)
11{  int i,res=x;
12   for (i=2; i<(int)sqrt(x*1)+1; i++)
13     {  if (x % i ==0)
14           {
15               res=res/i*(i-1);
16               while (x % i==0) x=x/i;
17           }

18     }

19    if (x>1) res=res/x*(x-1);
20    return res;
21
22}

23
24int main()
25{   cin >> T;
26    while (T--)
27    {  cin >> n;
28       cout << euler(n)<< endl;
29
30    }

31    return 0;
32}

33