欧拉函数φ(N)表示小于或等于N的正整数中与N互质的数的个数。又称φ函数、欧拉商数。
下面介绍欧拉函数的几个性质:
我们根据这几个性质就可以求出欧拉函数。
基本思路是首先置φ(N)=N,然后再枚举素数p,将p的整数倍的欧拉函数φ(kp)进行如下操作。
代码如下:
#include
using namespace std;
const int MAX = 1024;
int N;
int p[MAX], phi[MAX];
int main()
{
cin >> N;
for(int i = 1; i <=>N; i++)// 初始化
{ p[i] = 1; phi[i] = i; }
p[1] = 0;// 1不是素数
for(int i = 2; i <=>N; i++)// 筛素数
{
if(p[i])
{
for(int j = i * i; j <=>N; j += i)
{ p[j] = 0; }
}
}
for(int i = 2; i <=>N; i++)// 求欧拉函数
{
if(p[i])
{
for(int j = i; j <=>N; j += i)// 处理素因子p[i]
{
phi[j] = phi[j] / i * (i - 1);// 先除后乘,防止中间过程超出范围
}
}
}
cout <>'Primes: ' <>endl;
for(int i = 1; i <=>N; i++)
{ if(p[i]) { cout <>i <>' '; } }
cout <>endl;
cout <>'Euler Phi Function: ' <>endl;
for(int i = 1; i <=>N; i++)
{ cout <>phi[i] <>' '; }
return 0;
}
以上是关于欧拉函数的求法,对于它的应用,这里暂且介绍一个——求解原根的个数。
对于原根的定义,我们可以这样来叙述:
若存在一个实数a,使得( a^i ) mod N,a∈{1,2,3,⋯,N}的结果各不相同,我们就成实数a为N的一个原根。
原根的个数等于φ(φ(N))。这样我们就可以很方便的求出原根的个数。
代码如下:
#include
#include
using namespace std;
typedef unsigned long long ull;
ull N;
ull phi(ull x);
int main()
{
cin >> N;
cout <>phi(phi(N)) <>endl;
return 0;
}
ull phi(ull x)
{
ull ans = x;
ull m = (ull)sqrt(x);
for(ull i = 2; i <=>m; i++)
{
if(x % i == 0)// 求素因子
{
ans = ans / i * (i - 1);// 运用通项求解欧拉函数
while(x % i == 0)// 每个素因子只计算一次
{ x /= i; }
}
}
if(x > 1)// 防质数
{ ans = ans / x * (x - 1); }
return ans;
}
联系客服