Posted on 2010-08-13 22:58
MiYu 閱讀(1103)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM ( 數(shù)論 )
MiYu原創(chuàng), 轉(zhuǎn)帖請(qǐng)注明 : 轉(zhuǎn)載自 ______________白白の屋
題目描述:
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
新年快到了，“豬頭幫協(xié)會(huì)”準(zhǔn)備搞一個(gè)聚會(huì)，已經(jīng)知道現(xiàn)有會(huì)員N人，把會(huì)員從1到N編號(hào)，其中會(huì)長(zhǎng)的號(hào)碼是N號(hào)，凡是和會(huì)長(zhǎng)是老朋友的，那么該會(huì)員的號(hào)碼肯定和N有大于1的公約數(shù)，否則都是新朋友，現(xiàn)在會(huì)長(zhǎng)想知道究竟有幾個(gè)新朋友？請(qǐng)你編程序幫會(huì)長(zhǎng)計(jì)算出來(lái)。
Input
第一行是測(cè)試數(shù)據(jù)的組數(shù)CN（Case number，1<CN<10000），接著有CN行正整數(shù)N（1<n<32768），表示會(huì)員人數(shù)。
Output
對(duì)于每一個(gè)N，輸出一行新朋友的人數(shù)，這樣共有CN行輸出。
Sample Input
2
25608
24027
Sample Output
7680
16016
題目分析:
這題用 gcd 的話, 就 TLE 了, 很無(wú)語(yǔ), 所以只能用篩法了, 因?yàn)?num如果能整除 i ,i > 1, 那么對(duì)i 的倍數(shù), 肯定有大于1的公約數(shù).
其實(shí)題目就是求 和 num 互質(zhì) 的 數(shù)的個(gè)數(shù), 可以使用 euler 公式, 0ms 過(guò).
歐拉公式:
如果n的標(biāo)準(zhǔn)素因子分解式是p1^a1*p2^a2*……*pm^am，其中眾pj(j=1,2,……,m)都是素?cái)?shù)，
而且兩兩不等。則有 φ(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)
φ(n) 為 小于 n ,與n互質(zhì)的數(shù)的個(gè)數(shù).
篩法代碼:
#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;
}