数学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<bits/stdc++.h>
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<=a;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<<ans%mod;
return 0;
}
Comments NOTHING