P2261 [CQOI2007]余数求和

· · 题解

解题思路：

由题意得：ans=\sum_{i=1}^{n}k mod i
根据a mod b=a-b[\frac{a}{b}]
我们可以通过式子的转移算出$$ans=nk-\sum_{i=1}^{n}i*[\frac{k}{i}]$$ 我们用样例来列一个格来看看k/i的规律(见下表)

|i| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | -----------: | |[\frac{k}{i}] |5| 2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |0|

我们发现在某一段内一段连续的[\frac{k}{i}]是相同的，所以我们可以用除法分块来解决问题，首先，我们设

t=[\frac{k}{i}]

用l来代表我们当前除法块的左边界，r来代表右边界，我们让一开始的l=1，因为第一块除法块的开头永远都是从1开始（问为什么的去重新读题），然后我们可以通过l来求出r。

t=k/l;
if (t==0) r=n;
else r=min(k/t,n);

因为我们t的定义是t=[\frac{k}{i}] 所以我们可以直接让t=k/l来求出他当前除法块的商，因为连续一块除法块的商都是相等的（不相等就绝对不是同一块），这样我们算出了t，然后就通过t来找l

当t=0时，r=n。

当t!=0时，r=min（[\frac{k}{t}]，n）

解释如下，因为当t=0时，后面那一块肯定都是大于k的那一段，所以我们直接让r=n，算出最后这一大块，当t！=0的时候，我们让r=[\frac{k}{t}]，这样可以算出有这个整除的商的最大的一个整数是多少，因为[\frac{k}{t}]可能会大于n，所以我们加上一个min函数，防止他超过边界。 有了右边界，每一块的和也就好求了

每一块的和 = 当前块的 t \times 当前块元素个数 \times 当前块 i 的平均值 = t \times (r-l+1) \times (l+r) \div 2=t\times(r−l+1)\times(l+r)÷2
剩下的就是用n*k减去没一块的值就好了

代码如下：

#include<cstdio>
#include<cstdlib>
#include<cstring>
long long ans;
long long n,k;

long long min(long long x,long long y)
{
    return x<y?x:y;
}

int main()
{
    scanf("%lld %lld",&n,&k);
    ans=n*k;
    for (long long l=1,r,t;l<=n;l=r+1)//l，r就是解释里面的左右边界，t=k/i 
    {
        t=k/l;//求出当前的t 
        if (t==0) r=n;//如思路的
        else r=min(k/t,n);
        ans-=(t*(r-l+1)*(l+r)/2);
    }
    printf("%lld\n",ans);
}