首页 > 代码库 > 欧拉函数与欧拉打表解决实际问题

欧拉函数与欧拉打表解决实际问题

2024-07-14 09:08:49   229人阅读

 

1.欧拉函数的定义：

   欧拉函数phi(x)等于不超过x且与x互素的整数的个数。

2.欧拉函数的求法：推导过程见随笔《欧拉函数与容斥原理》.

3.代码实现欧拉函数：

 

 1 int euler_phi(int n) 2 { 3     int m=(int)sqrt(n+0.5);//取一半就行，简化计算 4     int ans=n; 5     for(int i=2;i<=m;i++) 6         if(n%i==0)//找素因子 7         { 8             ans=ans/i*(i-1);//公式的运用 9             while(n%i==0)n/=i;//除尽10         }11     if(n>1)ans=ans/n*(n-1);//如果除到最后还有一个数且是大于1的素数，那么采用同样的公式再算一次12 }

 

4.欧拉函数打表：（把一定范围内的整数的欧拉函数值存储起来）

 1 int phi[maxn]; 2 void phi_table(int n) 3 { 4     for(int i=2;i<=n;i++)phi[i]=0;//赋初值为0 5     phi[1]=1; 6     for(int i=2;i<=n;i++) 7         if(!phi[i]) 8             for(int j=i;j<=n;j+=i) 9             {10                 if(!phi[j])phi[j]=j;//素数一般都会赋初值为自身11                 phi[j]=phi[j]/i*(i-1);12             }13 }

5解决实际问题：

POJ 2478 ：

#include <iostream>#include <stdio.h>using namespace std;#define LL long longLL F[1000100];int phi[1000100];void phi_table(int n){    for(int i=2;i<=n;i++)phi[i]=0;    phi[1]=1;    for(int i=2;i<=n;i++)        if(!phi[i])            for(int j=i;j<=n;j+=i)            {                if(!phi[j])phi[j]=j;                phi[j]=phi[j]/i*(i-1);            }}int main(){    int n;    F[1]=0;    phi_table(1000000);    for(int i=2;i<=1000000;i++) F[i] = F[i-1]+phi[i];    while(scanf("%d",&n)&&n!=0){        cout<<F[n]<<endl;    }    return 0;}

欧拉函数打表能快速处理问题，一般不会超时。

 


联系
我们