[BZOJ 4173]数学【欧拉函数】

[Description]
(1<=n,m<=10^15)

[Solution]
/*出题人官方题解*/

[Code]
#include<cmath>
#include<cstdio>

typedef long long ll;
const int mod=998244353;

ll Phi(ll x){
    ll ans=x;
    for(int i=2,lim=sqrt(x)+1;i<lim;i++)
if(!(x%i)){
   ans=ans/i*(i-1);
   while(!(x%i)) x/=i;
}
    if(x>1) ans=ans/x*(x-1);
    return ans;
}

int main(){
    ll n,m;
    scanf("%lld%lld",&n,&m);
    printf("%lld",n%mod*(m%mod)%mod*(Phi(n)%mod)%mod*(Phi(m)%mod)%mod);
    return 0;
}

此博客中的热门博文

图论专题总结