题目:
找新朋友 |
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
Total Submission(s): 1882 Accepted Submission(s): 903 |
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
|
题意为求小于一个数的所有互质数,用欧拉公式求互质数:φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
n从1开始遍历到32768,对与每个n遍历它不大于32768的所有倍数,根据欧拉公式更新数组中的数值。n遍历完成则所求的所有数都打好表了……直接输出即可……
##代码如下
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iostream> #include <algorithm> #include <queue> #include <stack> #include <vector> #include <deque> #include <set> #include <map> #include <string> using namespace std; #define For(i,a) for(i=0;i<a;i++) #define Foru(i,a,b) for(i=a;i<=b;i++) #define Ford(i,a,b) for(i=a;i>=b;i--) #define clr(ar,vel) memset(ar,vel,sizeof(ar)) #define PB push_back typedef long long ll; const int maxint = 0x7fffffff; const ll maxll = 1LL<<60; const double EPS = 1e-10; // 素数筛法 const int prime_num = 32768; int prime[prime_num], cnt; void init(){ memset(prime, 0, sizeof(prime)); for(int i = 2; i < prime_num; i ++){ if( prime[i] ) continue; for(int j = i*i; j < prime_num; j += i) prime[j] = 1; } cnt = 0; for(int i = 2; i < prime_num; i ++){ if( !prime[i] ) prime[cnt++] = i; } } // 欧拉函数 phi() int phi(int x){ int res = x; for(int i = 0; i < cnt && prime[i] <= x; i ++) if( x % prime[i] == 0) res /= prime[i], res *= (prime[i] - 1); return res; } int main(){ #ifndef in ios::sync_with_stdio(false); #endif init(); int t, n; cin >> t; while(t--){ cin >> n; int x = *lower_bound(prime, prime+cnt, n); if( x == n) cout << n-1 << endl; else cout << phi(n) << endl; } return 0; }