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

点击量：219

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

目录

题目描述

给出正整数 $ 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;
}