Description
Input
输入仅有一行。
Output
输出共1行，由亍结果过大，所以请输出上式对998244353 取模的结果。
Sample Input
Sample Output
题解：
（吐槽：博客园的数学公式好慢……）
先%一发po姐……不看题解根本没思路啊……
$sum_{n=1}^{N}sum_{m=1}^{M}sum_{k=0}^{m-1}lfloorfrac{nk+x}{m} floor$
$我们先考虑后半部分$
$;;;\,sum_{k=0}^{m-1}lfloorfrac{nk+x}{m} floor$
$=sum_{k=0}^{m-1}lfloorfrac{nk-nk\,mod\, m+x+nk\,mod\,m}{m} floor$
$=sum_{k=0}^{m-1}lfloorfrac{nk\,mod\,m+x}{m} floor+sum_{k=0}^{m-1}frac{nk-nk\,mod\,m}{m}$
$考虑前半部分,同时设d=(n,m)$
$;;\,;sum_{k=0}^{m-1}lfloorfrac{nk\,mod\,m+x}{m} floor$
$=dsum_{k=0}^{frac{m}{d}-1}lfloorfrac{kd}{m} floor$
证明：首先设$（n，m）==d$，那么对同余方程$;;xnequiv kd(mod m)，kin[0,frac{m}{d}-1]$，我们知道一定存在整数解$x$，满足该式，同时有由于方程多解，且每个解的间隔应为$frac{m}{d}$，所以$kd$在$sum_{k=0}^{m-1}nk\,mod\,m$中共出先了$d$次
(我们仿照最开始将nk拆离的方法)
$=dsum_{k=0}^{frac{m}{d}-1}lfloorfrac{kd+x\,mod\,m+x-x\,mod\,m}{m} floor$
$=d(sum_{k=0}^{frac m d-1}lfloor frac{kd+x\,mod\,m}m floor+sum_{k=0}^{frac m d-1} frac{x-x\,mod\,m}m) $
$我们知道kd<m;;;xmod m<m $
$=d(sum_{k=0}^{frac m d-1}[kdgeq m-xmod m]+frac mdfrac{x-x\,mod\,m}m) $
$=d(sum_{k=0}^{frac md-1}[\,kgeqlceil frac{m-x\,mod\,m}{d} ceil\,]+frac{x-x\,mod\,m}{d})$
$=d(lfloorfrac{x\,mod\,m}{m} floor+lfloor frac xd floor-lfloor frac{x\,mod\,m}{d} floor)$
$=dlfloor frac xd floor$
我们再来看最开始另外两项
$1.sum_{k=0}^{m-1}frac{nk}m=frac nm frac{m(m-1)}2=frac{nm-n}{2}$
$2.sum_{k=0}^{m-1}frac{nk\,mod\,m}m(我们同样用到d)$
$=dsum_{k=0}^{frac md-1}frac{dk}m=frac {d^{2}}mfrac{frac md(frac md-1)}{2}=frac{m-d}{2}$
$Ans=sum_{n=1}^{N}sum_{m=1}^{M}(dlfloorfrac xd floor+frac {d+nm-n-m}2)$
$;;;;;;;\,=frac 12sum_{n=1}^{N}sum_{m=1}^{M}(2dlfloorfrac xd floor+ d+nm-n-m)$
$设S（n）=frac{n(n+1)}2$
$;;;;;;;\,=frac 12(sum_{n=1}^{N}sum_{m=1}^{M}(2dlfloorfrac xd floor+ d)+S(N)S(M)-MS(N)-NS(M))$
$;;;;;;;\,=frac 12(\,sum_{d=1}^{min(N,M)}(2dlfloorfrac xd floor+ d)sum_{t=1}^{min(lfloorfrac Nd floor,lfloorfrac Md floor)}mu(t)lfloor frac N{dt} floorlfloor frac M{dt} floor;+S(N)S(M)-MS(N)-NS(M)\,)$
对于后面我们O(1)求出即可，前面枚举每一个d带入计算即可。
时间复杂度$sum_{i=1}^{n}sqrt frac niapproxsqrt nint_{1}^{n}x^{-0.5}dx=2n-2sqrt n $
代码：
1 /************************************************************** 2 Problem: 4174 3 User: Troywar 4 Language: C++ 5 Result: Accepted 6 Time:964 ms 7 Memory:5100 kb 8 ****************************************************************/ 9 10 #include<cstdio> 11 #include<iostream> 12 using namespace std; 13 typedef long long ll; 14 const ll mod=998244353; 15 inline ll powmod(ll a, ll b){ 16 ll ans=1; 17 while(b){ 18 if(b&1) ans=ans*a%mod; 19 a=a*a%mod; 20 b>>=1; 21 }return ans; 22 } 23 inline ll S(int x){ 24 return 1LL*x*(x+1)/2%mod; 25 } 26 const int N=500000+1; 27 short miu[N]; 28 bool vis[N]; 29 int sum[N],prim[N/5],num; 30 double x; 31 inline void init (){ 32 miu[1]=sum[1]=1; 33 for(int i=2;i<N;i++){ 34 if(!vis[i]){ 35 miu[i]=-1; 36 prim[++num]=i; 37 }for(int j=1;i*prim[j]<N;j++){ 38 vis[i*prim[j]]=true; 39 if(i%prim[j]==0){ 40 miu[i*prim[j]]=0; 41 break; 42 }miu[i*prim[j]]=-miu[i]; 43 } 44 sum[i]=sum[i-1]+miu[i]; 45 } 46 47 } 48 inline ll get_sum(int n,int m){ 49 ll ans=0; 50 for(int i=1,pos;i<=n;i=pos+1){ 51 pos=min(n/(n/i),m/(m/i)); 52 ans+=1LL*(sum[pos]-sum[i-1])*(n/i)%mod*(m/i)%mod; 53 ans%=mod; 54 } 55 return (ans+mod)%mod; 56 } 57 int n,m; 58 int main(){ 59 scanf("%d%d%lf",&n,&m,&x); 60 init(); 61 ll ans=S(n)*S(m)%mod-S(n)*m%mod-S(m)*n%mod; 62 ans=(ans%mod+mod)%mod; 63 if(n>m) n^=m^=n^=m; 64 for(int i=1;i<=n;i++){ 65 ans+=(2ll*i*(ll)(x/i)+i)%mod*get_sum(n/i,m/i)%mod; 66 ans%=mod; 67 } 68 ans*=powmod(2,mod-2); 69 ans%=mod; 70 printf("%lld ",(ans+mod)%mod); 71 } 72 /* 73 15674 234561 126.156 74 */