P2260 [清华集训2012]模积和解题报告

解题报告

---

P2260 [清华集训2012]模积和解题报告：

更好的阅读体验

双倍经验：P2834 能力测验

题意

题意：求$\sum_{i=1}^n\sum_{j=1}^m[i\ne j](n\bmod i)\cdot(m\bmod j)$。

数据范围：$1\leqslant n,m\leqslant 10^9$。

分析

这是一道简单的推式子题，但是实现比较恶心。

首先不妨设$n\leqslant m$（如果$n>m$交换一下就好了）

然后可以用容斥将题目拆成两个部分：

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

将两个求和拆开：

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

因为取模很难搞，所以可以用一个性质$a\bmod b=a-\lfloor\frac{a}{b}\rfloor\cdot b$（取模的定义），将上式转换为：

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

将括号拆开，可以得到：

$$(n^2-\sum_{i=1}^ni\cdot\lfloor\frac{n}{i}\rfloor)\cdot(m^2-\sum_{i=1}^mi\cdot\lfloor\frac{m}{i}\rfloor)-\sum_{i=1}^n(nm-mi\cdot\lfloor\frac{n}{i}\rfloor-ni\cdot\lfloor\frac{m}{i}\rfloor+i^2\cdot\lfloor\frac{n}{i}\rfloor\cdot\lfloor\frac{m}{i}\rfloor)$$

此时我们的复杂度已经是$O(n)$了，然而这个复杂度仍然不足以通过本题。

要做这道题需要一个简单的技巧——整除分块。

我们很容易发现很多$\lfloor\frac{n}{i}\rfloor$的值是一样的，且所有的$\lfloor\frac{n}{i}\rfloor$为一个不下降子序列，呈块状分布

通过简单的计算可以得到，对于每个起点为$i$的块，它的值为$\lfloor\frac{n}{i}\rfloor$，终点为$\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$，然后我们就可以用$O(\sqrt{n})$的算法计算$\sum_{i=1}^ni\cdot \lfloor\frac{n}{i}\rfloor$了：

主要步骤，对于每一个块$[l,r]$，它乘号前面前缀和差分得到，即$(1+2+\cdots+r)-(1+2+\cdots+(l-1))$，乘号后面的就是$\lfloor\frac{n}{l}\rfloor$。

代码：

inline long long sum1(long long x){
    return x*(x+1)%mod*inv2%mod;
}
l=1,sum=n*n%mod;
while(l<=n){
    r=n/(n/l);
    sum=(sum-(sum1(r)-sum1(l-1)+mod)%mod*(n/l)%mod+mod)%mod;
    l=r+1;
}

同样，$\sum_{i=1}^mi\cdot \lfloor\frac{m}{i}\rfloor$的值也可以用相同的方法求得。

考虑求$\sum_{i=1}^n(nm-mi\cdot\lfloor\frac{n}{i}\rfloor-ni\cdot\lfloor\frac{m}{i}\rfloor+i^2\cdot\lfloor\frac{n}{i}\rfloor\cdot\lfloor\frac{m}{i}\rfloor)$，发现用整除分块完成它需要使区间$[l,r]$中所有的$i$都满足$\lfloor\frac{n}{i}\rfloor$与$\lfloor\frac{m}{i}\rfloor$相同。

可以用类似的方法，将上面代码中的r=n/(n/l);改为r=min(n/(n/l),m/(m/l));，然后就可以直接求值了！

且慢，虽然前三项$nm,mi\cdot\lfloor\frac{n}{i}\rfloor,ni\cdot\lfloor\frac{m}{i}\rfloor$都很容易求得，但是$i^2\cdot\lfloor\frac{n}{i}\rfloor\cdot\lfloor\frac{m}{i}\rfloor$不是很容易求，因为$(1^2+2^2+\cdots+i^2)$不好处理。

这里有一个简单的结论：$1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$，会在文后证明，现在先给出这一部分的代码：

inline long long sum2(long long x){
    return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;
}
l=1,tmp3=0;
while(l<=n){
    long long a,b,c;
    r=min(n/(n/l),m/(m/l));
    a=(r-l+1)*n%mod*m%mod;
    b=(sum1(r)-sum1(l-1)+mod)%mod*((n/l)*m%mod+(m/l)*n%mod)%mod;
    c=(sum2(r)-sum2(l-1)+mod)%mod*(n/l)%mod*(m/l)%mod;
    tmp3=(tmp3+a-b+c+mod)%mod;
    l=r+1;
}

代码

• 记得开long long
• 取模很恶心，如果错了多半是这种原因
• 因为三个整数相乘会爆long long，因此除法用逆元实现（逆元提前求得）

#include<stdio.h>
const long long mod=19940417,inv2=9970209,inv6=3323403;
long long i,j,k,m,n,l,r,ans,tmp1,tmp2,tmp3;
inline long long min(long long a,long long b){
    return a<b? a:b; 
}
inline void swp(long long &a,long long &b){
    a+=b,b=a-b,a-=b;
}
inline long long sum1(long long x){
    return x*(x+1)%mod*inv2%mod;
}
inline long long sum2(long long x){
    return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;
}
int main(){
    scanf("%lld%lld",&n,&m);
    if(n>m)
        swp(n,m);
    l=1,tmp1=n*n%mod;
    while(l<=n){
        r=n/(n/l);
        tmp1=(tmp1-(sum1(r)-sum1(l-1)+mod)%mod*(n/l)%mod+mod)%mod;
        l=r+1;
    }
    l=1,tmp2=m*m%mod;
    while(l<=m){
        r=m/(m/l);
        tmp2=(tmp2-(sum1(r)-sum1(l-1)+mod)%mod*(m/l)%mod+mod)%mod;
        l=r+1;
    }
    l=1,tmp3=0;
    while(l<=n){
        long long a,b,c;
        r=min(n/(n/l),m/(m/l));
        a=(r-l+1)*n%mod*m%mod;
        b=(sum1(r)-sum1(l-1)+mod)%mod*((n/l)*m%mod+(m/l)*n%mod)%mod;
        c=(sum2(r)-sum2(l-1)+mod)%mod*(n/l)%mod*(m/l)%mod;
        tmp3=(tmp3+a-b+c+mod)%mod;
        l=r+1;
    }
    ans=(tmp1*tmp2%mod-tmp3+mod)%mod;
    printf("%lld\n",ans);
    return 0;
} 

简单的证明

证明：

$$1^2+2^2+\cdots+n^2=\frac{n(n+1)(2n+1)}{6}$$

（这个式子可以用简单构造法与数学归纳法证明，由于大部分题解都是用的数学归纳法，且用数学归纳法读者自证不难，因此这里使用简单构造法）

由于有这样一个式子：$i^2=i^2-i+i(i-1)\cdot i+i$，因此我们可以将这个拆开：

$$1^2+2^2+\cdots+n^2=\sum_{i=1}^ni^2=\sum_{i=1}^n(i-1)\cdot i+\sum_{i=1}^ni$$

然后乘上$\frac{1}{3}$：

$$\sum_{i=1}^ni^2=\frac{1}{3}\sum_{i=1}^n(i-1)\cdot i\cdot3+\sum_{i=1}^ni$$

构造一下：

$$\sum_{i=1}^ni^2=\frac{1}{3}\sum_{i=1}^n(i-1)\cdot i\cdot((i+1)-(i-2))=\frac{1}{3}\sum_{i=1}^n(-(i-2)\cdot(i-1)\cdot i+(i-1)\cdot i\cdot(i+1))+\sum_{i=1}^ni$$

把它们全部展开：

$$\sum_{i=1}^ni^2=\frac{1}{3}(-(-1)\cdot0\cdot1+0\cdot1\cdot2-0\cdot1\cdot2+1\cdot2\cdot3-1\cdot2\cdot3+\cdots(n-1)\cdot n\cdot(n+1))+\frac{n\cdot(n+1)}{2}$$

发现括号里的很多项都可以抵消：

$$\sum_{i=1}^ni^2=\frac{(n-1)\cdot n\cdot(n+1)}{3}+\frac{n\cdot(n+1)}{2}=\frac{n\cdot(n+1)\cdot(2(n-1)+3)}{6}=\frac{n\cdot(n+1)\cdot(2n+1)}{6}$$

证毕。