BZOJ2956:模积和 数学

思路:

其实是一道简单题.关键是要注意到题目中的一个条件:\(i\not=j\)!!!

我们考虑用所有的情况减去\(i=j\)的情况.

所有的情况就很好求了.令\(f(n)=\sum_{i=1}^{n}n\%i\),则所有的情况为\(f(n)*{f(m)}\).

这玩意很容易分块求.

然后\(i=j\)的情况的贡献是:

\((n\%i)*(m\%i)=(n-i*\frac{n}{i})*(m-i*\frac{m}{i})=nm+i^2\frac{n}{i}\frac{m}{i}-n*i\frac{m}{i}-m*i\frac{n}{i}\)

这样发现分开之后都可以分块求.

于是就\(O(\sqrt{n})\)水过.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
static const int mod=19940417,rev2=(mod+1)>>1,rev6=3323403;
 
inline void mul(int&x,int y){x=(LL)x*y%mod;}
inline void inc(int&x,int y){if((x+=y)>=mod)x-=mod;}
inline void dec(int&x,int y){x=x<y?x+mod-y:x-y;}
inline int calc(int n){//return sigma i^2
    int res=n;mul(res,(LL)(n+1)*(2*n+1)%mod),mul(res,rev6);return res;
}
inline int cal(int l,int r){
    int cl=calc(l-1),cr=calc(r);
    return cr<cl?cr+mod-cl:cr-cl;
}
 
inline int solve1(int n,int lim){//return sigma i*(n/i)
    int lst,t,res=0;
    for(int i=1;i<=lim;i=lst+1){
        lst=min(lim,n/(n/i));
        mul(t=n/i,(LL)(i+lst)*(lst-i+1)%mod),mul(t,rev2);
        inc(res,t);
    }return res;
}
inline int solve2(int n){//return sigma n%i
    return ((LL)n*n%mod+mod-solve1(n,n))%mod;
}
inline int solve3(int n,int m,int lim){//return sigma i^2(n/i)(m/i)
    int lst,t,res=0;
    for(int i=1;i<=lim;i=lst+1){
        lst=min(n/(n/i),m/(m/i)),lst=min(lst,lim);
        mul(t=(LL)(n/i)*(m/i)%mod,cal(i,lst));
        inc(res,t);
    }return res;
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int res=(LL)solve2(n)*solve2(m)%mod;
    dec(res,(LL)min(n,m)*n%mod*m%mod);
    inc(res,(LL)solve1(n,min(n,m))*m%mod);
    inc(res,(LL)solve1(m,min(n,m))*n%mod);
    dec(res,solve3(n,m,min(n,m)));
    printf("%d",res);
    return 0;
}