Description
Input
输入仅有一行。
Output
输出共1行，由亍结果过大，所以请输出上式对998244353 取模的结果。
Sample Input
Sample Output
题解：
（吐槽：博客园的数学公式好慢……）
先%一发po姐……不看题解根本没思路啊……
$\sum_{n=1}^{N}\sum_{m=1}^{M}\sum_{k=0}^{m-1}\lfloor\frac{nk+x}{m} \rfloor$
$我们先考虑后半部分$
$\;\;\;\,\sum_{k=0}^{m-1}\lfloor\frac{nk+x}{m} \rfloor$
$=\sum_{k=0}^{m-1}\lfloor\frac{nk-nk\,\bmod\, m+x+nk\,\bmod\,m}{m} \rfloor$
$=\sum_{k=0}^{m-1}\lfloor\frac{nk\,\bmod\,m+x}{m} \rfloor+\sum_{k=0}^{m-1}\frac{nk-nk\,\bmod\,m}{m}$
$考虑前半部分,同时设d=(n,m)$
$\;\;\,\;\sum_{k=0}^{m-1}\lfloor\frac{nk\,\bmod\,m+x}{m} \rfloor$
$=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{kd}{m} \rfloor$
证明：首先设$（n，m）==d$，那么对同余方程$\;\;xn\equiv kd(\bmod m)，k\in[0,\frac{m}{d}-1]$，我们知道一定存在整数解$x$，满足该式，同时有由于方程多解，且每个解的间隔应为$\frac{m}{d}$，所以$kd$在$\sum_{k=0}^{m-1}nk\,\bmod\,m$*出先了$d$次
(我们仿照最开始将nk拆离的方法)
$=d\sum_{k=0}^{\frac{m}{d}-1}\lfloor\frac{kd+x\,\bmod\,m+x-x\,\bmod\,m}{m}\rfloor$
$=d(\sum_{k=0}^{\frac m d-1}\lfloor \frac{kd+x\,\bmod\,m}m \rfloor+\sum_{k=0}^{\frac m d-1} \frac{x-x\,\bmod\,m}m) $
$我们知道kd<m\;\;\;x\bmod m<m $
$=d(\sum_{k=0}^{\frac m d-1}[kd\geq m-x\bmod m]+\frac md\frac{x-x\,\bmod\,m}m) $
$=d(\sum_{k=0}^{\frac md-1}[\,k\geq\lceil \frac{m-x\,\bmod\,m}{d}\rceil\,]+\frac{x-x\,\bmod\,m}{d})$
$=d(\lfloor\frac{x\,\bmod\,m}{m}\rfloor+\lfloor \frac xd\rfloor-\lfloor \frac{x\,\bmod\,m}{d}\rfloor)$
$=d\lfloor \frac xd\rfloor$
我们再来看最开始另外两项
$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)$
$=d\sum_{k=0}^{\frac md-1}\frac{dk}m=\frac {d^{2}}m\frac{\frac md(\frac md-1)}{2}=\frac{m-d}{2}$
$Ans=\sum_{n=1}^{N}\sum_{m=1}^{M}(d\lfloor\frac xd \rfloor+\frac {d+nm-n-m}2)$
$\;\;\;\;\;\;\;\,=\frac 12\sum_{n=1}^{N}\sum_{m=1}^{M}(2d\lfloor\frac xd \rfloor+ d+nm-n-m)$
$设S（n）=\frac{n(n+1)}2$
$\;\;\;\;\;\;\;\,=\frac 12(\sum_{n=1}^{N}\sum_{m=1}^{M}(2d\lfloor\frac xd \rfloor+ d)+S(N)S(M)-MS(N)-NS(M))$
$\;\;\;\;\;\;\;\,=\frac 12(\,\sum_{d=1}^{min(N,M)}(2d\lfloor\frac xd \rfloor+ d)\sum_{t=1}^{\min(\lfloor\frac Nd\rfloor,\lfloor\frac Md\rfloor)}\mu(t)\lfloor \frac N{dt}\rfloor\lfloor \frac M{dt}\rfloor\;+S(N)S(M)-MS(N)-NS(M)\,)$
对于后面我们O(1)求出即可，前面枚举每一个d带入计算即可。
时间复杂度$\sum_{i=1}^{n}\sqrt \frac ni\approx\sqrt n\int_{1}^{n}x^{-0.5}dx=2n-2\sqrt n $
代码：
/**************************************************************
Problem: 4174
User: Troywar
Language: C++
Result: Accepted
Time:964 ms
Memory:5100 kb
****************************************************************/ #include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll mod=;
inline ll powmod(ll a, ll b){
ll ans=;
while(b){
if(b&) ans=ans*a%mod;
a=a*a%mod;
b>>=;
}return ans;
}
inline ll S(int x){
return 1LL*x*(x+)/%mod;
}
const int N=+;
short miu[N];
bool vis[N];
int sum[N],prim[N/],num;
double x;
inline void init (){
miu[]=sum[]=;
for(int i=;i<N;i++){
if(!vis[i]){
miu[i]=-;
prim[++num]=i;
}for(int j=;i*prim[j]<N;j++){
vis[i*prim[j]]=true;
if(i%prim[j]==){
miu[i*prim[j]]=;
break;
}miu[i*prim[j]]=-miu[i];
}
sum[i]=sum[i-]+miu[i];
} }
inline ll get_sum(int n,int m){
ll ans=;
for(int i=,pos;i<=n;i=pos+){
pos=min(n/(n/i),m/(m/i));
ans+=1LL*(sum[pos]-sum[i-])*(n/i)%mod*(m/i)%mod;
ans%=mod;
}
return (ans+mod)%mod;
}
int n,m;
int main(){
scanf("%d%d%lf",&n,&m,&x);
init();
ll ans=S(n)*S(m)%mod-S(n)*m%mod-S(m)*n%mod;
ans=(ans%mod+mod)%mod;
if(n>m) n^=m^=n^=m;
for(int i=;i<=n;i++){
ans+=(2ll*i*(ll)(x/i)+i)%mod*get_sum(n/i,m/i)%mod;
ans%=mod;
}
ans*=powmod(,mod-);
ans%=mod;
printf("%lld\n",(ans+mod)%mod);
}
/*
15674 234561 126.156
*/