欧拉函数

数学3（欧拉函数） P13880 [蓝桥杯 2023 省 Java A] 互质数的个数 看完题面后很容易想到欧拉函数， 但是 a^b 是一个很大的数， 考虑一些特殊的性质：\varphi (p^n)=(p-1)p^{n-1}，（p 为质数） 所以令 a=\prod ^n _{i=1} p_i^{\alpha _i}， 所以 a^b=\prod ^n _{i=1} p_i^{b\alpha _i} 因为欧拉函数是积性函数， 所以 \varphi (a^b)=\prod ^n _{i=1} \varphi(p_i^{b\alpha _i})=\prod ^n _{i=1} (p_i-1)p_i^{b\alpha _i-1} 代码： #include using namespace std; #define int unsigned long long const int mod=998244353; int a,b,ans=1; int mi(int x,int y){ int ans=1; while(y){ if(y%2) ans*=x,ans%=mod; y/=2,x=x*x%mod; } return ans; } signed main(){ cin>>a>>b; int x=a; for(int i=2;i*i1) ans=(ans*(x-1)%mod*mi(x,b-1)%mod)%mod; cout `#include using namespace std; #define int unsigned long long const int mod=998244353; int a,b,ans=1; int mi(int x,int y){ int ans=1; while(y){ if(y%2) ans*=x,ans%=mod; y/=2,x=x*x%mod; } return ans; } signed main(){ cin>>a>>b; int x=a; for(int i=2;i*i int p=i,arf=0; while(x%i==0) x/=i,arf++; if(arf) ans=(ans*(p-1)%mod*mi(p,arf*b-1))%mod; } if(x>1) ans=(ans*(x-1)%mod*mi(x,b-1)%mod)%mod; cout return 0; }` P2568 GCD \begin{align} &\sum_{p\in prime}^n \sum_{i=1}^n \sum_{j=1}^n [(i,j)=p] \\ =&\sum_{p\in prime}^n \sum_{i=1}^{⌊n/p⌋} \sum_{j=1}^{⌊n/p⌋} [(i,j)=1] \\ =&\sum_{p\in prime}^n (2\sum_{i=1}^{⌊n/p⌋} \varphi (i) -1) ^{^*(1)} \end{align} 预处理欧拉函数的前缀和即可。 ^*(1)：由于 (i,j) 与 (j,i) 是等价的，所以只需要计算 i 的因子，并把统计结果乘二即可。但是当且仅当 i=j=p 会重复计算，所以减去一个一即可。 代码： #include using namespace std; #define int long long const int N=1e7+5; int n,idx,ans; int vis[N],prm[N],phi[N]; void euler(){ phi[1]=1; for(int i=2;i>n; euler(); for(int i=1;i `#include using namespace std; #define int long long const int N=1e7+5; int n,idx,ans; int vis[N],prm[N],phi[N]; void euler(){ phi[1]=1; for(int i=2;i if(!vis[i]){ prm[++idx]=i; phi[i]=i-1; } for(int j=1;1ll*i*prm[j] vis[i*prm[j]]=1; if(i%prm[j]==0){ phi[i*prm[j]]=phi[i]*prm[j]; break; } else phi[i*prm[j]]=phi[i]*(prm[j]-1); } } } signed main(){ cin>>n; euler(); for(int i=1;iphi[i]+=phi[i-1]; for(int i=1;iphi[n/prm[i]]*2-1; cout return 0; }` P4388 付公主的矩形 如上图，我们把 n 拆成了 2*2，也就是两个日字形，而对于每个日字形，满足周长的一半等于 2+1。 这样说可能比较抽象，我们再举一个例子： 如上图，我们把 n 拆成了 1*4，而对于整个矩形，满足周长的一半等于 4+1。 也就是说，我们需要首先分解 n 的因数，之后根据因数找到大矩形，且满足矩形周长的一半等于因数加一，但是这个显然只是一个特征，并不能用来得出答案。 但是当我们仔细分析以上两张图的区别，为什么第一张图的对角线会经过一个点？ 原因在于大矩形的两边不互质，所以导致有一个等比缩小的矩形与其对角线斜率一致。 所以我们在分解完因数后，枚举小矩形边长，判断是否互质即可。 代码： #include using namespace std; #define int long long int n,ans; int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); } signed main(){ cin>>n; for(int i=1;i*i `#include using namespace std; #define int long long int n,ans; int gcd(int a,int b){ if(b==0) return a; return gcd(b,a%b); } signed main(){ cin>>n; for(int i=1;i*i if(n%i!=0) continue; int x=i+1,y=n/i+1; for(int j=1;2*j int a=j,b=x-j; if(gcd(a,b)==1) ans++; } if(x!=y) for(int j=1;2*j int a=j,b=y-j; if(gcd(a,b)==1) ans++; } } cout return 0; }` P5091 【模板】扩展欧拉定理 欧拉定理： 当 a,m\in Z，且 gcd(a,m)=1 时有： a^{φ(m)}\equiv 1 \ (mod \ m)。 所以 a^{b}\equiv a^{bmodφ(m)} \ (mod \ m)。 扩展欧拉定理： 当 a,m\in Z 时有： $$ a^b \equiv \begin{cases} a^b &b则有代码： #include using namespace std; #define int long long int a,m,p; int phi(int n){ int r=n; for(int i=2;i*i1) r=r/n*(n-1); return r; } int qp(int x,int y,int mod){ int r=1; while(y){ if(y&1) r=r*x%mod; x=x*x%mod; y>>=1; } return r; } signed main(){ cin>>a>>m; p=phi(m); string s; cin>>s; bool f=0; int b=0; for(int i=0;i=p){ f=1; b%=p; } } if(f) cout `#include using namespace std; #define int long long int a,m,p; int phi(int n){ int r=n; for(int i=2;i*i if(n%i==0){ r=r/i*(i-1); while(n%i==0) n/=i; } } if(n>1) r=r/n*(n-1); return r; } int qp(int x,int y,int mod){ int r=1; while(y){ if(y&1) r=r*x%mod; x=x*x%mod; y>>=1; } return r; } signed main(){ cin>>a>>m; p=phi(m); string s; cin>>s; bool f=0; int b=0; for(int i=0;is.size();i++){ char c=s[i]; b=b*10+(c-'0'); if(b>=p){ f=1; b%=p; } } if(f) coutqp(a,b+p,m); else coutqp(a,b,m); return 0; }`