Luogu P2260 [ Tsinghua training 2012] Modular product sum Answer key

Topic link ：P2260 [ Tsinghua training 2012] Modular product sum

The question ：

seek
$$\left(\sum _{i=1}^n\sum _{j=1}^m(n\mathrm{m}\mathrm{o}\mathrm{d}i)\times (m\mathrm{m}\mathrm{o}\mathrm{d}j),i\ne j\right)\mathrm{m}\mathrm{o}\mathrm{d}19940417$$

According to the principle of inclusion and exclusion
$$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^m(n\mathrm{m}\mathrm{o}\mathrm{d}i)\times (m\mathrm{m}\mathrm{o}\mathrm{d}j),i\ne j \\ =\sum _{i=1}^n\sum _{j=1}^m(n\mathrm{m}\mathrm{o}\mathrm{d}i)\times (m\mathrm{m}\mathrm{o}\mathrm{d}j)-\sum _{i=1}^n(n\mathrm{m}\mathrm{o}\mathrm{d}i)\times (m\mathrm{m}\mathrm{o}\mathrm{d}i) \end{gathered}$$
Then push the persimmon
$$\begin{array}{rl}& \sum _{i=1}^n\sum _{j=1}^m(n\mathrm{m}\mathrm{o}\mathrm{d}i)\times (m\mathrm{m}\mathrm{o}\mathrm{d}j)-\sum _{i=1}^n(n\mathrm{m}\mathrm{o}\mathrm{d}i)\times (m\mathrm{m}\mathrm{o}\mathrm{d}i)\\ & =\sum _{i=1}^n\left(n-i\lfloor \frac{n}{i}\rfloor \right)\times \sum _{j=1}^m\left(m-j\lfloor \frac{m}{j}\rfloor \right)-\sum _{i=1}^n\left(n-i\lfloor \frac{n}{i}\rfloor \right)\times \left(m-i\lfloor \frac{m}{i}\rfloor \right)\\ & =\left(n^2-\sum _{i=1}^{n}i\lfloor \frac{n}{i}\rfloor \right)\times \left(m^2-\sum _{i=1}^{m}i\lfloor \frac{m}{i}\rfloor \right)-\sum _{i=1}^n\left(nm-mi\lfloor \frac{n}{i}\rfloor -ni\lfloor \frac{m}{i}\rfloor +i^2\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor \right)\\ & =\left(n^2-\sum _{i=1}^{n}i\lfloor \frac{n}{i}\rfloor \right)\times \left(m^2-\sum _{i=1}^{m}i\lfloor \frac{m}{i}\rfloor \right)-n^{2}m+\sum _{i=1}^n\left(mi\lfloor \frac{n}{i}\rfloor +ni\lfloor \frac{m}{i}\rfloor -i^2\lfloor \frac{n}{i}\rfloor \lfloor \frac{m}{i}\rfloor \right)\end{array}$$
There is a small formula , There's no proof （ flee
$$\sum _{i=1}^n{i}^2=\frac{n(n+1)(2n+1)}{6}$$
Then there's no difficulty here

Consider number theory blocking

The code is as follows

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int p=19940417;
const int inv2=9970209;
const int inv6=3323403;
#define sum1(x) ((x)%p*(x+1)%p*inv2%p)
#define sum2(x) ((x)%p*(x+1)%p*(2*(x)%p+1)%p*inv6%p)
int solve(int x)
{
    
    int res=x%p*x%p;
    for(int l=1,r; l<=x; l=r+1)
    {
    
        r=x/(x/l);
        res=(res-(sum1(r)-sum1(l-1))%p*(x/l)%p)%p;
    }
    return res;
}
int n,m,a,b,c,ans;
signed main()
{
    
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> m;
    if(n>m)swap(n,m);
    ans=(solve(n)*solve(m)%p-n%p*n%p*m%p)%p;
    for(int l=1,r; l<=n; l=r+1)
    {
    
        r=min(n/(n/l),m/(m/l));
        a=(a+(sum1(r)-sum1(l-1))%p*m%p*(n/l)%p)%p;
        b=(b+(sum1(r)-sum1(l-1))%p*n%p*(m/l)%p)%p;
        c=(c+(sum2(r)-sum2(l-1))%p*(n/l)%p*(m/l)%p)%p;
    }ans=((ans+a+b-c)%p+p)%p;
    cout << ans << endl;
    return 0;
}

Reprint please explain the source