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
西風蕭瑟 閱讀(984)
評論(0) 編輯 收藏 引用 所屬分類:
數學