洛谷 P2261 [CQOI2007]余数求和 题解【数学】【同余】

点击量：41

数学题（听说对学莫比乌斯反演有用？

目录

题目描述

给出正整数 \(n​\) 和 \(k​\) 计算 \(G(n, k)=k\ \bmod\ 1 + k\ \bmod\ 2 + k\ \bmod\ 3 + \cdots + k\ \bmod\ n​\) 的值

其中 \(k\ \bmod\ i​\) 表示 \(k​\) 除以 \(i​\) 的余数。

例如
\(G(10, 5)=5\ \bmod\ 1 + 5\ \bmod\ 2 + 5\ \bmod\ 3 + 5\ \bmod\ 4 + 5\ \bmod\ 5 \cdots + 5\ \bmod\ 10\)
\(=0+1+2+1+0+5+5+5+5+5=29\)

输入输出格式

输入格式：

两个整数 \(n​\) ，\(k​\)

输出格式：

答案

输入输出样例

输入样例#1：

10 5

输出样例#1：

29

说明

\(30\%: n , k \le 1000​\)

\(60\%: n , k \le 10^6​\)

\(100\%: n , k \le 10^9​\)

题解：

这个题是去年8月开的坑。期间好像看过题解，这次学莫比乌斯反演的时候做这个题，答案出得挺快的。

把模转化为商定义。
$$
a\bmod b=a-\left\lfloor\frac{a}{b}\right\rfloor\cdot b
$$
然后套回原式子得
$$
\sum_{i=1}^n k\bmod i=\sum_{i=1}^n\left(k-\left\lfloor\frac{k}{i}\right\rfloor\cdot i\right)=nk-\sum_{i=1}^n\left\lfloor\frac{k}{i}\right\rfloor\cdot i
$$
但是实际上由于\(k​\)的因数最多只有 \(O(\sqrt k)​\) 个，所以也只会出现最多 \(O(\sqrt k)​\) 个 \(\left\lfloor\frac{k}{i}\right\rfloor​\)，而对于连续的 \(i​\)，\(\left\lfloor\frac{k}{i}\right\rfloor​\) 是一样的。

令 \(t=\left\lfloor\frac{k}{i}\right\rfloor​\)，则对于 \(\left\lfloor\frac{k}{i}\right\rfloor​\) 相等的一段 \([l,r]​\)，在 \(\sum​\) 做出的贡献是 \(-\sum_{i=l}^r ti​\)。

因此我们每当找到一个新的 \(\left\lfloor\frac{k}{i}\right\rfloor​\) 时，就要确定一个 \(r​\) 然后跳过去。计算\([l,r]​\)这段等差数列即可，数列中\(a_1=tl,d=t,n=(r-l+1)​\)。

（写了个等差数列求和的函数有点麻烦

要注意对于比 \(k​\) 大的那部分 \(i​\) 在 \(\sum​\) 所做的贡献均为 \(0​\) .

Code：

#include<cstdio>
int Min(int x,int y)//注意对n取min
{
    return x<y?x:y;
}
long long calc(long long a,long long d,long long n)
{
    return a*n+n*(n-1)*d/2;
}
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    long long ans=(long long)n*k;
    for(int i=1;i<=k&&i<=n;++i)
    {
        ans-=calc((long long)i*(k/i),k/i,Min(n,k/(k/i))-i+1);
        i=Min(n,k/(k/i));
    }
    printf("%lld\n",ans);
    return 0;
}