清华集训2012 模积和题解

$\text{Description}$

求

$\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j), i \neq j$

$n,m\le 10^9$

$\text{Solution}$

发现 $i\neq j$ 很让人不爽，考虑容斥掉：

$\sum_{i=1}^{n} \sum_{j=1}^{m} (n \bmod i) \times (m \bmod j)-\sum_{i=1}^{\min(n,m)}(n\bmod{i})(m\bmod{i})$

考虑 $a\bmod{b}=a-b\lfloor\dfrac{a}{b}\rfloor$，有：

$\sum_{i=1}^n(n-i\lfloor\dfrac{n}{i}\rfloor)\sum_{j=1}^m(m-j\lfloor\dfrac{m}{j}\rfloor)-\min(n,m)nm-$ $\sum_{i=1}^{\min(n,m)}i^2\lfloor\dfrac{n}{i}\rfloor\lfloor\dfrac{m}{i}\rfloor+m\sum_{i=1}^{\min(n,m)}i\lfloor\dfrac{n}{i}\rfloor+n\sum_{i=1}^{\min(n,m)}i\lfloor\dfrac{m}{i}\rfloor$

前两个就是余数求和的套路，对于后面，考虑 $\sum_{i=1}^ni$ 和 $\sum_{i=1}^n i^2$ 都可以 $O(1)$ 求得，故前缀和十分容易得到，从而用数论分块解决。

$\text{Code}$

#include<bits/stdc++.h>
#define REG register
#define MOD 19940417
#define LL long long
using namespace std;
inline LL read(){
    REG LL x(0);
    REG char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=(x*10)+(c^48),c=getchar();
    return x;
}
inline LL Min(LL a,LL b){return a<b?a:b;}

LL n,m;

LL ans;

inline LL get1(LL l,LL r){return (r-l+1)%MOD;}
inline LL getId(LL l,LL r){return (l+r)*(r-l+1)%MOD*9970209%MOD;}
inline LL getId2(LL l,LL r){return (r*(r+1)%MOD*(2*r+1)%MOD*3323403%MOD-(l-1)*(l)%MOD*(2*l-1)%MOD*3323403%MOD+MOD)%MOD;}

inline LL divId(LL n,LL m){
    LL l=1,r=0,ans=0;
    for(;l<=m;l=r+1)
        r=Min(m,n/(n/l)),ans=(ans+getId(l,r)*(n/l)%MOD)%MOD;
    return ans;
}
inline LL divId2(LL n,LL m){
    LL l=1,r=0,ans=0;
    for(;l<=m;l=r+1)
        r=Min(m,n/(n/l)),ans=(ans+getId2(l,r)%MOD*3323403%MOD);
    return ans;
}
inline LL divId2(LL n,LL m,LL k){
    LL l=1,r=0,ans=0;
    for(;l<=k;l=r+1)
        r=Min(Min(k,n/(n/l)),m/(m/l)),ans=(ans+getId2(l,r)*(n/l)%MOD*(m/l)%MOD);
    return ans;
}

int main(){
    n=read(),m=read();
    ans=(n*n%MOD-divId(n,n)+MOD)%MOD;
    ans=(m*m%MOD-divId(m,m)+MOD)%MOD*ans%MOD;
    LL g=Min(n,m);
    ans=(ans-g*n%MOD*m%MOD+MOD)%MOD;
    ans=(ans-divId2(n,m,g)+MOD)%MOD;
    ans=(ans+m*divId(n,g)%MOD)%MOD;
    ans=(ans+n*divId(m,g)%MOD)%MOD;
    printf("%lld\n",ans);
}

2021-03-20

CF Chapter2 简要题解

CodeForces

清华集训2012 模积和题解