欧拉函数
定义
\(\varphi(n)\) 表示小于等于\(n\)的与\(n\)互质的数的个数。
性质
- \(\varphi\)为积性函数，即\(\varphi(a\cdot b)=\varphi(a)\cdot\varphi(b)\) \((a\perp b)\)
- 根据定义可知，$\varphi(p)=p-1 $ \((p\in prime)\)
- 根据定义可知，\(\varphi(p^k)=p^k-p^{k-1}\)
- 由第一分解定理，设\(n=\prod_{i=1}^r p_i^{k_i}\) \(\varphi(n)=n\cdot\prod_{i=1}^r\frac{p_i-1}{p_i}=n\cdot\prod_{i=1}^r(1-\frac{1}{p_i})\)
- \(n=\sum_{d|n}\varphi(d)\)
欧拉定理
若\(\gcd(a,b)=1\)，则\(a^{\varphi(b)}\equiv 1\pmod b\)
当\(b\in prime\) \(a^{b-1}\equiv 1\pmod b\)就是费马小定理
扩展欧拉定理
\[a^b\equiv\begin{cases} a^{b\mod\varphi(p)} &\gcd(a,p)=1\\ a^b &\gcd(a,p)\ne1,b\le\varphi(p)\\ a^{b\mod\varphi(p)+\varphi(p)} &\gcd(a,p)\ne1,b>\varphi(p) \end{cases}\pmod p \]线性筛欧拉函数
int ss[N],cnt,vs[N],fi[N];
il void init(int n){
for(ri int i=2;i<=n;++i){
if(!vs[i]) ss[++cnt]=i,fi[i]=i-1;
for(ri int j=1;j<=cnt&&ss[j]*i<=n;++j){
vs[i*ss[j]]=1;
if(i%ss[j]) fi[i*ss[j]]=fi[i]*fi[ss[j]];
else{fi[i*ss[j]]=fi[i]*ss[j];break;}
}
}
return;
}
求一个数的欧拉函数
il int fi(int n){
int as=n,res=n;
for(ri int i=2;i*i<=res;++i){
if(res%i==0){
while(res%i==0) res/=i;
as=as/res*(res-1);
}
}
if(res>1) as=as/res*(res-1);
return as;
}
资料
一些题目
1.P2158 [SDOI2008] 仪仗队
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs cosnt
#define ri register
using namespace std;
const int N=40001;
int fi[N],b[N],cnt,ss[664580],mx;
inline int done(const int &n){
if(!n) return 0;//
register int ans=3;
for(register int i=2;i<=n;++i){
if(!b[i]) ss[++cnt]=i,fi[i]=i-1;
for(register int j=1;j<=cnt&&ss[j]*i<=n;++j){
b[i*ss[j]]=1;
if(i%ss[j]) fi[i*ss[j]]=fi[i]*fi[ss[j]];
else{fi[i*ss[j]]=fi[i]*ss[j];break;}
}
ans+=2*fi[i];
}
return ans;
}
int main(){
int n;
cin>>n;
cout<<done(n-1);
return 0;
}
2.P5091 【模板】扩展欧拉定理
AC·code
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a1,p1,b1;
int fp;
int ksmqm(int a,int b,int p){
int x=1;
while(b){
if(b%2) x=(x*a)%p;
a=(a*a)%p,b/=2;
}
return x%p;
}
int mod(int p){
int x=0;
int f=0;
char c=getchar();
while(c==' '||c=='\n'||c=='\r') c=getchar();
while(c>='0'&&c<='9'){
x=(x<<1)+(x<<3)+(c^48);
if(x>=p) f=1;
x%=p;
c=getchar();
}
//b>=fp 扩欧式子才成立，aaaaaaaaaa
return x+p*f;
}
int ko(int p){
int ans=1;
for(int i=2;i<=p;i++){
int x=1,y=0;
while(p%i==0){
y=x,x*=i,p/=i;
}
ans*=(x-y);
if(p==1) break;
}
return ans;
}
signed main(){
cin>>a1>>p1;
fp=ko(p1);
b1=mod(fp);
int b2=fp;
while(b1>b2){
b2=b1;
b1=b1%fp+fp;
}
cout<<ksmqm(a1,b1,p1);
return 0;
}
3.P4139 上帝与集合的正确用法
AC·code
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
register bool f=x=0;register char c=getchar();
while(c<'0'||c>'9') f|= (c=='-'), c=getchar();
while(c>='0'&c<='9')x=x*10+(c^48),c=getchar();
}
inline void wt(int x){
if(x<0) putchar('-'),x=-x;
if(x>=10) wt(x/10);
putchar(x%10+48);
}
const int T=1e3+1,N=1e7+1;
int t,p[T],fi[N],b[N],cnt,ss[664580],mx;
inline void init(const int &n){
for(register int i=2;i<=n;++i){
if(!b[i]) ss[++cnt]=i,fi[i]=i-1;
for(register int j=1;j<=cnt&&ss[j]*i<=n;++j){
b[i*ss[j]]=1;
if(i%ss[j]) fi[i*ss[j]]=fi[i]*fi[ss[j]];
else{fi[i*ss[j]]=fi[i]*ss[j];break;}
}
}
}
inline int qpow(register int a,register int b,const int &m){
register int ans=1;
while(b){
if(b&1) ans=(1ll*ans*a)%m;
a=(1ll*a*a)%m,b>>=1;
}
return ans;
}
inline int done(const int &m){
if(m==1) return 0;
return qpow(2,done(fi[m])+fi[m],m);
}
int main(){
rd(t);
for(register int i=1;i<=t;++i){
rd(p[i]),mx=max(mx,p[i]);
}
init(mx);
for(register int i=1;i<=t;++i){
wt(done(p[i])),putchar('\n');
}
return 0;
}
4.Power Tower
AC·code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
int n,m,q,w[N];
map<int,int> fi;
inline int rd(){
register int x=0;register char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
return x;
}
inline void wt(int x){
if(x>=10) wt(x/10);
putchar(x%10+48);
}
inline void getfi(int n){
register int ans=n,nn=n;
for(int i=2;i*i<=n;i++){
if(nn%i==0){
ans/=i;ans*=(i-1);
while(nn%i==0) nn/=i;
}
}
if(nn>1) ans/=nn,ans*=(nn-1);
fi[n]=ans;
}
inline int qpow(int a,int b,int p){
register int ans=1;
while(b>0){
if(b&1){
ans=ans*a;
if(ans>=p) ans=ans%p+p;
}
a=a*a;
if(a>=p) a=a%p+p;
b>>=1;
}
return ans;
}
inline int done(int i,int p,int r){
if(i>r||p==1) return 1;
return qpow(w[i],done(i+1,fi[p],r),p);
}
signed main(){
n=rd(),m=rd();
for(register int i=1;i<=n;i++) w[i]=rd();
register int ff=m;
while(ff!=1) getfi(ff),ff=fi[ff];fi[ff]=1;
q=rd();
register int l,r;
while(q--){
l=rd(),r=rd();
wt(done(l,m,r)%m),putchar('\n');
}
}
5.P2568 GCD
AC·code
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
using namespace std;
cs int N=1e7+9;
int b[N],ss[N],tot,fi[N];
il void init(int n){
fi[1]=1;
for(ri int i=2;i<=n;++i){
if(!b[i]) ss[++tot]=i,fi[i]=i-1;
b[i]=tot;
for(ri int j=1;j<=tot&&ss[j]*i<=n;++j){
b[i*ss[j]]=1;
if(i%ss[j]) fi[i*ss[j]]=fi[i]*fi[ss[j]];
else{fi[i*ss[j]]=fi[i]*ss[j];break;}
}
}
}
int main(){
int n;
long long as=0;
cin>>n;
init(n);
for(ri int i=2;i<n;++i){
as+=fi[i]*b[n/i];
}
cout<<as*2+tot;
return 0;
}
6.3.P2398 GCD SUM
莫比乌斯反演里写过了，这里不再赘述
7.LCMSUM - LCM Sum
莫比乌斯反演里写过了，这里也不再赘述
8.拿行李（极限版） GCD - Extreme (II)
点击查看代码
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long
using namespace std;
il int rd(){
ri int x=0,f=1;ri char c=getchar();
while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
return x*f;
}
il void wt(int x){
if(x<0) x=-x,putchar('-');
ri short tl=0,a[15]={0};
do{a[++tl]=x%10,x/=10;}while(x);
for(;tl;--tl)putchar(a[tl]+48);
}
cs int N=4e6+1;
int ss[N+5],cnt,vs[N+5],fi[N+5];
int n,m,as[N];
il void init(int n){
as[1]=fi[1]=0;
for(ri int i=2;i<=n;++i){
if(!vs[i]) ss[++cnt]=i,fi[i]=i-1;
for(ri int j=1;j<=cnt&&ss[j]*i<=n;++j){
vs[i*ss[j]]=1;
if(i%ss[j])fi[i*ss[j]]=fi[i]*fi[ss[j]];
else{fi[i*ss[j]]=fi[i]*ss[j];break;}
}
as[i]=fi[i];
}
for(ri int i=2;i*i<=n;++i){
as[i*i]+=fi[i]*i;
for(ri int j=i+1;j*i<=n;++j){
as[j*i]+=fi[i]*j+fi[j]*i;
}
}
for(ri int i=2;i<=n;++i) as[i]+=as[i-1];
}
signed main(){
init(N);
n=rd();
while(n){
wt(as[n]);
putchar('\n');
n=rd();
}
return 0;
}