http://acm.hdu.edu.cn/showproblem.php?pid=1787
/***
count the number of the integers M (0<M<N) which satisfies gcd(N,M)>1.
即：N - 1 - phi(N)
由于1<N<100000000, 不肯能预处理所有的欧拉函数
采用欧拉性质：
1.若n是质数p的k次幂，φ（n）= （p-1）p^(k-1)
2.若m，n互质，φ（mn）= φ(m)φ(n)
若 n =p1^a1 * p2^a2 *
* pn^an
则 phi(n) = (p1-1)*p1^(a1-1) * (p2-1)*p2^(a2-1) ** (pn-1)*pn^(an-1)
= N * (p1-1)*(p2-2)**(pn-1)/(p1*p2**pn)
**/
#include <stdio.h>
#define N 10001
__int64 p[5000];
int hash[10001];
int main()
{
__int64 i, j, ans, n, m, temp;
p[0] = 1; //记录素数个数
p[1] = 2;
for (i=3; i<N; i+=2)
{
if (hash[i])
continue;
p[++p[0]] = i;
for (j=i*i; j<N; j+=i)
hash[j] = 1;
} //筛素数
while (scanf("%I64d", &n), n)
{
ans = 1;
m = n;
for (i=1; p[i]<=m && i<=p[0]; i++)
if (m%p[i]==0)
{
temp = 1;
while (m%p[i] == 0)
{
m /= p[i];
temp *= p[i];
}
temp /= p[i];
ans*=(p[i]-1)*temp;
}
if (m>1)
{
ans *= (m-1);
} //如果剩下那个数大于1,m为大于10000的质数
printf("%I64d\n", n-ans-1);
}
}
posted on 2009-12-02 20:34
西风萧瑟 阅读(946)
评论(0) 编辑 收藏 引用 所属分类:
数学