poj2407 欧拉定理解题报告报告

Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
Input

就是求小于n且与n互质的数的个数

这题使用到欧拉函数：
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。例如φ(8)=4，因为1,3,5,7均和8互质。

φ函数的值
　　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
　　若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
　　欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
　　特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。

证明略

举例：
　　ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４；
　　ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；
　　ψ（４９）＝４９×（１－１/７）＝４２。

我的代码：
#include<cstdio>
#include<iostream>
using namespace std;
#include<cmath>
int num[100000];
int f_Euler(int s,int a)//返回欧拉数的个数，s是数组num里数据的个数，a是原来输入数据，即n
{
double ans=a;
int i;
for(i=1;i<=s;i++)
{
   ans*=(1-1.0/num[i]);
}
return (int)(ans+0.1);
}
int main()
{
num[0]=1;//无用
int a,b,s,i,max,t;
while(scanf("%d",&a)&& a)
{
   t=a;
   s=0;
   //以下为分解质因数
   max=sqrt(double(a))+1;
   if(a%2==0){
    while(a%2==0){
     a=a/2;
    }
    num[++s]=2;
   }
   for(int i=3;i<=max;i+=2)
   {
    if(a%i==0){
     while(a%i==0){
      a=a/i;
     }
     num[++s]=i;
    }
   }
   if(a!=1)num[++s]=a;//分解最后剩下的数（可能大于sqrt(n)）
   printf("%d\n",f_Euler(s,t));
   memset(num,0,sizeof(int)*s);
}
return 0;
}

poj上一个优化的代码：
while(scanf("%d",&n),n != 0){
        if(n == 1){
            printf("0\n"); continue;
        }
        ans = n;
        for(int i = 2;i*i <= n;++i){
            if( n % i == 0 ){
                ans = ans - ans/i;//见注释
                while(n%i == 0){
                    n /= i;
                }
            }
        }
        // n is prime itself
        if(n != 1) ans = ans - ans / n;
        printf("%d\n",ans);
    }
注释：
ans = ans - ans/i其实就是
欧拉定理ans*=(1-1.0/num[i]);的简化版，深入理解欧拉函数后就知道是：ans/i是小于等于ans被i整除的数的个数..

附：
2-100欧拉函数表（供测试用）
　　n φ(n)
　　2 1
　　3 2
　　4 2
　　5 4
　　6 2
　　7 6
　　8 4
　　9 6
　　10 4
　　11 10
　　12 4
　　13 12
　　14 6
　　15 8
　　16 8
　　17 16
　　18 6
　　19 18
　　20 8
　　21 12
　　22 10
　　23 22
　　24 8
　　25 20
　　26 12
　　27 18
　　28 12
　　29 28
　　30 8
　　31 30
　　32 16
　　33 20
　　34 16
　　35 24
　　36 12
　　37 36
　　38 18
　　39 24
　　40 16
　　41 40
　　42 12
　　43 42
　　44 20
　　45 24
　　46 22
　　47 46
　　48 16
　　49 42
　　50 20
　　51 32
　　52 24
　　53 52
　　54 18
　　55 40
　　56 24
　　57 36
　　58 28
　　59 58
　　60 16
　　61 60
　　62 30
　　63 36
　　64 32
　　65 48
　　66 20
　　67 66
　　68 32
　　69 44
　　70 24
　　71 70
　　72 24
　　73 72
　　74 36
　　75 40
　　76 36
　　77 60
　　78 24
　　79 78
　　80 32
　　81 54
　　82 40
　　83 82
　　84 24
　　85 64
　　86 42
　　87 56
　　88 40
　　89 88
　　90 24
　　91 72
　　92 44
　　93 60
　　94 46
　　95 72
　　96 32
　　97 96
　　98 42
　　99 60
　　100 40

推荐订阅源

明明如月成长笔记