Posted on 2010-08-13 22:58
MiYu 閱讀(1107)
評論(0) 編輯 收藏 引用 所屬分類:
ACM ( 數論 )
MiYu原創, 轉帖請注明 : 轉載自 ______________白白の屋
題目描述:
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): 1868 Accepted Submission(s): 809
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
題目分析:
這題用 gcd 的話, 就 TLE 了, 很無語, 所以只能用篩法了, 因為 num如果能整除 i ,i > 1, 那么對i 的倍數, 肯定有大于1的公約數.
其實題目就是求 和 num 互質 的 數的個數, 可以使用 euler 公式, 0ms 過.
歐拉公式:
如果n的標準素因子分解式是p1^a1*p2^a2*……*pm^am，其中眾pj(j=1,2,……,m)都是素數，
而且兩兩不等。則有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
φ(n) 為 小于 n ,與n互質的數的個數.
篩法代碼:
#include <iostream>
using namespace std;
int p[40000];
int euler ( int num )
{
memset ( p , 0, sizeof (p) );
int cnt = 0;
for ( int i = 2; i <= num / 2; ++ i )
{
if ( num % i == 0 && p[i] == 0 )
{
for ( int j = i; j < num; j += i )
{
if ( p[j] == 0 )
cnt ++;
p[j] = 1 ;
}
}
}
return num - cnt - 1;
}
int main ()
{
int T;
scanf ( "%d",&T );
while ( T -- )
{
int num;
scanf ( "%d",&num );
printf ( "%d\n",euler ( num ) );
}
return 0;
}
歐拉代碼: ( AC_Quester 神牛代碼 <----0rz )
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
int eular(int n)
{
int ret=1,i;
for (i=2;i*i<=n;i++)
{
if (n%i==0)
{
n/=i,ret*=i-1;
while (n%i==0)
n/=i,ret*=i;
}
}
if (n>1)
ret*=n-1;
return ret;
}
int main()
{
int n ,a ;
scanf("%d",&n);
while(n--)
{
scanf("%d",&a);
int res = eular(a);
printf("%d\n",res);
}
return 0;
}