题解 P2260 【[清华集训2012]模积和】

whiteqwq · 2020-07-14 20:34:23 · 题解

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交换一下就好了）

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

将两个求和拆开：

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

将括号拆开，可以得到：

此时我们的复杂度已经是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;
} 

简单的证明

证明：

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

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

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

构造一下：

把它们全部展开：

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

证毕。