[bzoj4173]数学

xiaoxiao2021-02-27  193

题目大意

懒得写

推导

[n mod k+m mod kk]=[nnkk+mmkk>=k] 于是等价于 [n+mknkmk>=1] 注意这个式子的值也只可能是0或1,因此可以写成 n+mknkmk 代入原式 n+mk=1(n+mknkmk)ϕ(k) 展开来 n+mk=1n+mkϕ(k)nk=1nkϕ(k)mk=1mkphi(k) 注意到 ni=1niϕ(i)=ni=1d|iϕ(d)=ni=1i 于是你就奥妙重重的发现刚刚那条式子等于nm。 至于前面那个phi(n)和phi(m)随便求一下。

#include<cstdio> #include<algorithm> #include<cmath> #define fo(i,a,b) for(i=a;i<=b;i++) using namespace std; typedef long long ll; const int mo=998244353; ll i,j; ll n,m,l,k,t,ans; int main(){ scanf("%lld%lld",&n,&m); ans=(n%mo)*(m%mo)%mo; k=l=n; t=floor(sqrt(n)); fo(i,2,t){ if (k%i==0){ l=l/i*(i-1); while (k%i==0) k/=i; } } if (k>1) l=l/k*(k-1); ans=ans*(l%mo)%mo; k=l=m; t=floor(sqrt(m)); fo(i,2,t){ if (k%i==0){ l=l/i*(i-1); while (k%i==0) k/=i; } } if (k>1) l=l/k*(k-1); ans=ans*(l%mo)%mo; printf("%lld\n",ans); }
转载请注明原文地址: https://www.6miu.com/read-12906.html

最新回复(0)