[清华集训]模积和

Description

Solution

egin{equation}
egin{aligned}
& sum_{i=1}^n sum_{j=1}^m (nmod i)(mmod j)[i!=j]\
= & sum_{i=1}^n sum_{j=1}^m (nmod i)(mmod j)-sum_{i=1}^n(nmod i)(mmod i)\
= & sum_{i=1}^n (n-lfloor frac ni floor i) sum_{j=1}^m (m- lfloor frac mj floor j)-sum_{i=1}^n(nmod i)(mmod i)\
= & (n^2 - sum_{i=1}^n lfloor frac ni floor i)(m^2 - sum_{j=1}^m lfloor frac mj floor j)- sum_{i=1}^n(nmod i)(mmod i)\
= & (n^2 - sum_{i=1}^n lfloor frac ni floor i)(m^2 - sum_{j=1}^m lfloor frac mj floor j)- sum_{i=1}^n(n- lfloor frac ni floor i)(m - lfloor frac mi floor i)\
= & (n^2 - sum_{i=1}^n lfloor frac ni floor i)(m^2 - sum_{j=1}^m lfloor frac mj floor j)- sum_{i=1}^n (nm - im lfloor frac ni floor - in lfloor frac mi floor + i^2 lfloor frac ni floor lfloor frac mi floor)\
= & (n^2 - sum_{i=1}^n lfloor frac ni floor i)(m^2 - sum_{j=1}^m lfloor frac mj floor j)- mn^2sum_{i=1}^n (- im lfloor frac ni floor - in lfloor frac mi floor + i^2 lfloor frac ni floor lfloor frac mi floor)\
end{aligned}
end{equation}

数论分块AC

模数不是质数，~~淦~~

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
long long n,m,temp1,temp2,temp3,mod2,mod6;
const long long mod=19940417;
inline long long read()
{
    long long w=0,f=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        w=(w<<1)+(w<<3)+ch-'0';
        ch=getchar();
    }
    return w*f;
}
long long s1(long long x)
{
    return x%mod*(x+1)%mod*mod2%mod;
}
long long s2(long long x)
{
    return x%mod*(x+1)%mod*(2*x+1)%mod*mod6%mod;
}
int main()
{
    n=read();
    m=read();
    mod2=9970209;
    mod6=3323403;
    temp1=n*n%mod;
    temp2=m*m%mod;
    for(long long i=1;i<=n;)
    {
        long long j=n/(n/i);
        temp1-=(s1(j)-s1(i-1)+mod)%mod*(n/i)%mod;
        (temp1+=mod)%=mod;
        i=j+1;
    }
    for(long long i=1;i<=m;)
    {
        long long j=m/(m/i);
        temp2-=(s1(j)-s1(i-1)+mod)%mod*(m/i)%mod;
        (temp2+=mod)%=mod;
        i=j+1;
    }
    if(n>m)
        swap(n,m);
    temp3=n*n%mod*m%mod;
    for(long long i=1;i<=n;)
    {
        long long j=min(n/(n/i),m/(m/i));
        temp3+=(s2(j)-s2(i-1)+mod)%mod*(n/i)%mod*(m/i)%mod;
        ((temp3%=mod)+=mod)%=mod;
        temp3-=(s1(j)-s1(i-1)+mod)%mod*n%mod*(m/i)%mod;
        ((temp3%=mod)+=mod)%=mod;
        temp3-=(s1(j)-s1(i-1)+mod)%mod*m%mod*(n/i)%mod;
        ((temp3%=mod)+=mod)%=mod;
        i=j+1;
    }
    printf("%lld
",((temp1*temp2%mod-temp3)%mod+mod)%mod);
    return 0;
}