連結:http://acm.hdu.edu.cn/showproblem.php?pid=1286
題目:
找新朋友
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 7213 Accepted Submission(s): 3759
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-1個數中與n互質的數。最容易想到的做法就是,暴力,将前n-1個數枚舉一遍,用輾轉相除法來判斷最大公約數是否為1,但是這樣做會逾時。這個題目正确的做法應該是歐拉方程,φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn為x的所有質因數,x是不為0的整數,φ(x)表示前x-1個數中與x互質的數的個數,例如φ(8) = 8 * (1 - 1/2)。這裡,我們可以進行優化,用素數篩選法将質數算出來,利用素數表求x的質因子。
代碼:
#include <cstdio>
#include <cstring>
const int MAXN = 32770;
int num = 0, prime[MAXN];
bool isprime[MAXN];
int fun(int n)
{
int ret = n;
for(int i = 0; i < num && prime[i] <= n; i++)
{
if(0 == n % prime[i])
{
ret = ret - ret / prime[i];
}
}
return ret;
}
int main()
{
memset(isprime, true, sizeof(isprime));
for(int i = 2; i < MAXN; i++)
{
if(isprime[i]) prime[num++] = i;
for(int j = 0; j < num && i * prime[j] < MAXN; j++)
{
isprime[i * prime[j]] = false;
if(0 == i % prime[j]) break;
}
}
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
printf("%d\n", fun(n));
}
return 0;
}