题解 P2261 【[CQOI2007]余数求和】

· · 题解

这个题是我们学校模拟赛时出的题，我考试的时候并没有想到除法分块，而是自创了一种算法：%法分块（魔法分块）

首先大家都知道，除法是可以分块的。那我们就想，取余运算是不是也可以分块呢？

答案是可以的。不过分块的方式要特殊一些。（成等差数列）

设i=n/k+1

从k开始往前k-n/i个数分为一块，可以通过手模发现该块呈等差数列，公差为(i-1)

从n/i开始往前n/i-n/(i+1)个数分为一块，该块也呈等差数列，公差为i

……

以此类推，直到没有项数≥2的等差数列了为止

还有些坑点在代码里qwq

下面上代码：

#include<bits/stdc++.h>
using namespace std;
long long n,ans,i,s,an,k;
long long qh(long long a1,long long d,long long n){//等差数列求和
    an=(n-1)*d+a1;//求末项
    return (a1+an)*n/2;//求通项
}
int main(){
    scanf("%lld%lld",&k,&n);
    if(k>n)ans+=(k-n)*n,k=n;//n比k大的特殊处理（在本程序中，n与k是反的qwq
    i=n/k+1;//公差+1的值，也可用来计算分块范围
    s=k;//分块起点
    while(n/(i-1)>1+n/i){//如果还能进行分块运算（就是还有两个及以上的数呈等差数列）
        ans+=qh(n%s,i-1,s-n/i);//ans为答案
        s=n/i;//更新分块起点
        i++;//更新公差+1（更新范围）
    }
    for(long long j=1;j<=n/(i-1);j++)
        ans+=n%j;//剩下的数一个一个加
    printf("%lld\n",ans);
    return 0;
}