题目大意：求∑Nn=1∑Mm=1∑m?1k=0?nk+xm? mod 998244353<script type="math/tex" id="MathJax-Element-111">\sum_{n=1}^N\sum_{m=1}^M\sum_{k=0}^{m-1}\lfloor\frac{nk+x}m\rfloor\ mod\ 998244353</script>

如果n<script type="math/tex" id="MathJax-Element-112">n</script>和m<script type="math/tex" id="MathJax-Element-113">m</script>都已经确定了。如今要求这坨玩应：
∑m?1k=0?nk+xm?<script type="math/tex" id="MathJax-Element-114">\sum_{k=0}^{m-1}\lfloor\frac{nk+x}m\rfloor</script>
=∑m?1k=0(?nk%m+xm?+nk?nk%mm)<script type="math/tex" id="MathJax-Element-115">=\sum_{k=0}^{m-1}(\lfloor\frac{nk\%m+x}m\rfloor+\frac{nk-nk\%m}m)</script>
=∑m?1k=0(?nk%m+xm?+nkm?nk%mm)<script type="math/tex" id="MathJax-Element-116">=\sum_{k=0}^{m-1}(\lfloor\frac{nk\%m+x}m\rfloor+\frac{nk}m-\frac{nk\%m}m)</script>

我们一项一项考虑

令d=gcd(n,m)<script type="math/tex" id="MathJax-Element-117">d=\gcd(n,m)</script>，那么有

∑m?1k=0?nk%m+xm?<script type="math/tex" id="MathJax-Element-118">\sum_{k=0}^{m-1}\lfloor\frac{nk\%m+x}m\rfloor</script>
=d?∑md?1k=0?kd+xm?<script type="math/tex" id="MathJax-Element-119">=d*\sum_{k=0}^{\frac md-1}\lfloor\frac{kd+x}m\rfloor</script>
=d?(md?x?x%mm+∑md?1k=0?kd+x%mm?)<script type="math/tex" id="MathJax-Element-120">=d*(\frac md*\frac{x-x\%m}m+\sum_{k=0}^{\frac md-1}\lfloor\frac{kd+x\%m}m\rfloor)</script>
=d?(md?x?x%mm+∑md?1k=0[kd+x%m≥m])<script type="math/tex" id="MathJax-Element-121">=d*(\frac md*\frac{x-x\%m}m+\sum_{k=0}^{\frac md-1}[kd+x\%m\geq m])</script>
=d?(x?x%md+?x%md?)<script type="math/tex" id="MathJax-Element-122">=d*(\frac{x-x\%m}d+\lfloor\frac{x\%m}d\rfloor)</script>
=d??xd?<script type="math/tex" id="MathJax-Element-123">=d*\lfloor\frac xd\rfloor</script>

∑m?1k=0nkm=nm?m?(m?1)2=n?m?n2<script type="math/tex" id="MathJax-Element-124">\sum_{k=0}^{m-1}\frac{nk}m=\frac nm*\frac{m*(m-1)}2=\frac{n*m-n}2</script>

∑m?1k=0nk%mm=d?∑md?1k=0kdm=d2m?(md?1)?md2=m?d2<script type="math/tex" id="MathJax-Element-125">\sum_{k=0}^{m-1}\frac{nk\%m}m=d*\sum_{k=0}^{\frac md-1}\frac{kd}m=\frac{d^2}m*\frac{(\frac md-1)*\frac md}2=\frac{m-d}2</script>

故答案为
∑Nn=1∑Mm=1(d??xd?+n?m?n2?m?d2)<script type="math/tex" id="MathJax-Element-126">\sum_{n=1}^N\sum_{m=1}^M(d*\lfloor\frac xd\rfloor+\frac{n*m-n}2-\frac{m-d}2)</script>
=12?∑Nn=1∑Mm=1(2?d??xd?+d+n?m?n?m)<script type="math/tex" id="MathJax-Element-127">=\frac12*\sum_{n=1}^N\sum_{m=1}^M(2*d*\lfloor\frac xd\rfloor+d+n*m-n-m)</script>
=12?(S(N)?S(M)?S(N)?m?S(M)?n+∑min(N,M)d=1(d+2?d??xd?)∑min(?Nd?,?Md?)k=1μ(k)??Nd?k???Md?k?)<script type="math/tex" id="MathJax-Element-128">=\frac12*(S(N)*S(M)-S(N)*m-S(M)*n+\sum_{d=1}^{min(N,M)}(d+2*d*\lfloor\frac xd\rfloor)\sum_{k=1}^{min(\lfloor\frac Nd\rfloor,\lfloor\frac Md\rfloor)}\mu(k)*\lfloor\frac N{d*k}\rfloor*\lfloor\frac M{d*k}\rfloor)</script>

当中S(n)=n?(n+1)2<script type="math/tex" id="MathJax-Element-129">S(n)=\frac{n*(n+1)}2</script>

然后O(nlogn)<script type="math/tex" id="MathJax-Element-130">O(nlogn)</script>枚举d<script type="math/tex" id="MathJax-Element-131">d</script>和k<script type="math/tex" id="MathJax-Element-132">k</script>就可以

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 500500
#define MOD 998244353
using namespace std;
int n,m,x;
long long ans;
int mu[M];
int prime[M],tot;
bool not_prime[M];
void Linear_Shaker()
{
    int i,j;
    mu[1]=1;
    for(i=2;i<=500000;i++)
    {
        if(!not_prime[i])
        {
            prime[++tot]=i;
            mu[i]=MOD-1;
        }
        for(j=1;prime[j]*i<=500000;j++)
        {
            not_prime[prime[j]*i]=true;
            if(i%prime[j]==0)
            {
                mu[prime[j]*i]=0;
                break;
            }
            mu[prime[j]*i]=(MOD-mu[i])%MOD;
        }
    }
}
long long Sum(long long n)
{
    return (n*(n+1)>>1)%MOD;
}
int main()
{
    int i,j;
    cin>>n>>m>>x;
    Linear_Shaker();
    ans=((Sum(n)*Sum(m)-Sum(n)*m-Sum(m)*n)%MOD+MOD)%MOD;
    if(n>m) swap(n,m);
    for(i=1;i<=n;i++)
    {
        long long temp=i+x/i*i*2;
        for(j=1;j*i<=n;j++)
            (ans+=temp*mu[j]%MOD*(n/i/j)%MOD*(m/i/j)%MOD)%=MOD;
    }
    cout<<(ans*(MOD+1>>1)%MOD)<<endl;
    return 0;
}