洛谷 P2261 [CQOI2007]余数求和 题解【数学】【同余】
点击量:48
数学题(听说对学莫比乌斯反演有用?
题目描述
给出正整数 \(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;
}
说点什么