首先这一题用的是欧拉函数!!函数!!不是什么欧拉公式!!
欧拉函数求的就是题目要求的数。
关于欧拉函数的模板网上百度一下到处都是,原理也容易找,这里要介绍一下另一个强势模板。
在这一题的讨论里看到的。
上题上代码。
-----------------------------------------------------------------------------------
新年快到了,“猪头帮协会”准备搞一个聚会,已经知道现有会员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
Author
SmallBeer(CML)
1 #include <iostream> 2 #include <cstring> 3 #include <cmath> 4 #include <cstdio> 5 #include <iomanip> 6 7 using namespace std; 8 9 typedef long long ll; 10 const int INF = 0x3f3f3f3f; 11 const int MAXN = 35000; 12 const int MOD = 1e9+7; 13 14 int euler(int n) 15 { 16 int ret = n; 17 for(int i = 2;i * i <= n;++i) 18 { 19 if(n % i == 0) 20 { 21 ret = ret - ret / i; 22 while(n % i == 0) 23 n /= i; 24 } 25 } 26 if(n > 1) 27 ret = ret - ret / n; 28 return ret; 29 } 30 31 int main() 32 { 33 int T; 34 cin >>T; 35 while(T--) 36 { 37 int n; 38 cin >>n; 39 cout <<euler(n)<<endl; 40 } 41 return 0; 42 }
关于if(n > 1):例如n = 12 = 3 * 4,先得到的 i 是2,然后n = 3,就跳出来了,因为循环的判断条件是 i * i <= n。