Posted on 2010-08-13 22:58
MiYu 阅读(1091)
评论(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;
}