Description

求 \(\sum_{i=1}^n\sum_{j=1}^m(n\%i)*(m\%j)\),\(i!=j\)

Solution

写成这样的形式：

\(\sum_{i=1}^{n}\sum_{j=1}^{m}(n-\lfloor\frac{n}{i}\rfloor*i)*(m-\lfloor\frac{m}{j}\rfloor*j)\)

暴力拆即可，注意 \(i=j\) 的情况，减去下式即可

\(\sum_{i=1}^{min(n,m)}(n\%i)*(m\%i)\)

模数不是质数，手算一个6的逆元即可

#include 
    
     using namespace std;typedef long long ll;const int mod=19940417;int inv=3323403;inline int S(int n){return 1ll*n*(n+1)/2%mod;}inline int G(int n){return 1ll*n*(n+1)%mod*(2*n+1)%mod*inv%mod;}void work(){    int n,m;    cin>>n>>m;    if(n>m)swap(n,m);    ll ni=0,mj=0,rc=0;    for(int i=1,r;i<=n;i=r+1){        r=n/(n/i);        ni=(ni+1ll*(n/i)*(1ll*S(r)-S(i-1)+mod)%mod)%mod;    }    for(int j=1,r;j<=m;j=r+1){        r=m/(m/j);        mj=(mj+1ll*(m/j)*(1ll*S(r)-S(j-1)+mod)%mod)%mod;    }    for(int i=1,r;i<=n;i=r+1){        r=min(n/(n/i),m/(m/i));        rc=(rc+1ll*(n/i)*(m/i)%mod*(1ll*G(r)-G(i-1)+mod)%mod)%mod;    }    rc=(rc+1ll*n*n%mod*m%mod-ni*m%mod)%mod;    for(int i=1,r;i<=n;i=r+1){        r=min(n,m/(m/i));        rc=(rc-1ll*(m/i)*(1ll*S(r)-S(i-1)+mod)%mod*n%mod)%mod;    }    ll ans=1ll*n*n%mod*m%mod*m%mod;    ans=ans-mj*n%mod*n%mod-ni*m%mod*m%mod+ni*mj%mod-rc;    ans%=mod;if(ans<0)ans+=mod;    printf("%lld\n",ans);}int main(){    freopen("pp.in","r",stdin);    freopen("pp.out","w",stdout);    work();    return 0;}