欧拉函数、欧拉定理、费马小定理（附例题）
发布时间
阅读量：
阅读量
欧拉函数
欧拉函数的公式可以用容斥原理证明。
欧拉函数的求法1：O(n*sqrt(n))
ACWING873欧拉函数
给定 n 个正整数 ai ，请你求出每个数的欧拉函数。
欧拉函数的定义
输入格式
第一行包含整数 n 。
接下来 n 行，每行包含一个正整数 ai 。
输出格式
输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
数据范围
1≤n≤100 ,
1≤ai≤2×109
输入样例：
3
3
6
8输出样例：
2
2
4AC代码：
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,a,res;
cin>>n;
while(n--)
{
cin>>a;
res=a;
for(int i=2;i<=a/i;i++)
{
if(a%i==0)
{
res=res/i*(i-1);
while(a%i==0)a=a/i;
}
}
if(a>1)res=res/a*(a-1);
cout<<res<<'\n';
}
return 0;
}注意点：
- 用到了试除法
res=res/i*(i-1);可以避免出现小数，影响计算结果。
欧拉函数求法2：线性筛法 O(n)
给定一个正整数 n ，求 1∼n 中每个数的欧拉函数之和。
输入格式
共一行，包含一个整数 n 。
输出格式
共一行，包含一个整数，表示 1∼n 中每个数的欧拉函数之和。
数据范围
1≤n≤106
输入样例：
6输出样例：
12AC代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int st[N],primes[N],phi[N],cnt;
void get_eulers(int n)
{
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!st[i])
{
primes[cnt++]=i;
phi[i]=i-1;
}
for(int j=0;primes[j]<=n/i;j++)
{
st[primes[j]*i]=1;
if(i%primes[j]==0)
{
phi[primes[j]*i]=phi[i]*primes[j];
break;
}
phi[primes[j]*i]=phi[i]*(primes[j]-1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
long long res;
cin>>n;
get_eulers(n);
for(int i=1;i<=n;i++)res+=phi[i];
cout<<res;
return 0;
}注意点：
本题采用线性筛法作为基础模板，并在此基础上进行了必要的优化。
对于phi[1]的情况，则直接赋值即可。
当i为质数时，则有phi[i]=i-1。
其中primes[j]表示i的一个质因子，则满足关系式：phi[primes[j]*i]=phi[i]*primes[j];。
而如果primes[j]不是i的一个质因子，则有关系式：phi[primes[j]i]=phi[i](primes[j]-1);。
欧拉定理和费马定理
了解一下，无代码
全部评论 (0)
还没有任何评论哟~