zcmimi's blog
avatar
zc
2020-03-12 13:03:00
  • 本文总阅读量
查看原题

点击跳转

\sum_{i=1}^n\sum_{j=1}^m[i≠j](n \bmod i)(m \bmod j),n,m\le 10^9

数论分块

先不考虑i!=j

\sum_{i=1}^n\sum_{j=1}^m(n \bmod i)(m \bmod j) \\ =\sum_{i=1}^n(n-i\left \lfloor \frac ni\right \rfloor)\sum_{j=1}^m(m-j\left \lfloor \frac mj\right \rfloor)

考虑i=j,设k=\min(n,m)

\sum_{i=1}^n\sum_{j=1}^m(n \bmod i)(m \bmod j)[i=j] \\ =\sum_{i=1}^k(n \bmod i)(m \bmod i) \\ =\sum_{i=1}^k(n-i\left \lfloor \frac ni \right \rfloor)(m-i\left \lfloor \frac mi \right \rfloor) \\ =\sum_{i=1}^knm-ni\left \lfloor \frac mi \right \rfloor-mi\left \lfloor \frac ni \right \rfloor+i^2 \left \lfloor \frac{nm}{i^2}\right \rfloor \\ =knm-n\sum_{i=1}^k i\left \lfloor \frac mi \right \rfloor-m\sum_{i=1}^ki\left \lfloor \frac ni \right \rfloor+\sum_{i=1}^ki^2\left \lfloor \frac ni \right \rfloor\left \lfloor \frac mi \right \rfloor

两个相减就是答案

提示: \sum_{i=1}^n{i^2}=\frac{n(n+1)(2n+1)}6

推导过程:

S=\sum_{i=1}^n{i^2}

(n+1)^3-n^3=3n^2+3n+1

n^3-(n-1)^3=3(n-1)^2+3(n-1)+1

\cdots

2^3-1^3=3\times1^2+3\times 1+1

上面n个式子相加得到:

(n+1)^3-1=3(1^2+2^2+\dots+n^2)+3(1+2+\dots+n)+n

\therefore S=\frac13\left[ (n+1)^3-1- \frac12n(n+1) \right]=\frac{n(n+1)(2n+1)}6

#include<cstdio>
const int P=19940417;
inline int min(int x,int y){return x<y?x:y;}
inline int sum(int l,int r){return 1ll*(l+r)*(r-l+1)/2%P;}
inline int mi(int n){return 1ll*n*(n+1)%P*(2*n+1)%P*3323403%P;}
inline int SUM(int l,int r){return (mi(r)-mi(l-1)+P)%P;}
inline int calc(int k){
    int ans=1ll*k*k%P;
    for(int l=1,r=0;l<=k;l=r+1){
        r=k/(k/l);
        ans=(ans-1ll*sum(l,r)*(k/l)%P+P)%P;
    }
    return ans;
}
int main(){
    int n,m,ans,k;
    scanf("%d%d",&n,&m);
    ans=1ll*calc(n)*calc(m)%P;
    k=min(n,m);
    ans=(ans-1ll*k*n%P*m%P+P)%P;
    for(int l=1,r=0;l<=k;l=r+1){
        r=min(n/(n/l),m/(m/l));
        ans=(ans+1ll*n*sum(l,r)%P*(m/l)%P)%P;
        ans=(ans+1ll*m*sum(l,r)%P*(n/l)%P)%P;
        ans=(ans-1ll*SUM(l,r)*(n/l)%P*(m/l)%P+P)%P;
    }
    printf("%d\n",ans);
}
BZ 2956 模积和
comment评论
Search
search