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]<=&& 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 西风萧瑟 阅读(891) 评论(0)  编辑 收藏 引用 所属分类: 数学

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理