题目链接:http://acm.sdibt.edu.cn/JudgeOnline/problem.php?id=1227 
题意:计算比n小的与n互质的数的个数,可以利用欧拉函数实现,可以用下面的的函数φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数,x是不为0的整数。。

code:#include <stdio.h>
#include <stdlib.h>
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;
    while(scanf("%d",&n)&&n)
    {
        printf("%d\n",eular(n));
    }
    return 0;
} 
菜鸟之作,仅供参考,如有错误,请您提出——Tamara

发表评论

电子邮件地址不会被公开。

Post Navigation