题目大意

懒得写

推导

[n mod k+m mod k≥k]=[n−⌊nk⌋k+m−⌊mk⌋k>=k] 于是等价于 [⌊n+mk⌋−⌊nk⌋−⌊mk⌋>=1] 注意这个式子的值也只可能是0或1，因此可以写成 ⌊n+mk⌋−⌊nk⌋−⌊mk⌋ 代入原式 ∑n+mk=1(⌊n+mk⌋−⌊nk⌋−⌊mk⌋)ϕ(k) 展开来 ∑n+mk=1⌊n+mk⌋ϕ(k)−∑nk=1⌊nk⌋ϕ(k)−∑mk=1⌊mk⌋phi(k) 注意到 ∑ni=1⌊ni⌋ϕ(i)=∑ni=1∑d|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); }