资讯详情

原题

题目描述

给出正整数\(n\)和\(k\), 请计算

\[G(n, k) = \sum_{i=1}^{n} k \bmod i \]

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

输入格式

输入只有一行两个整数，分别表示\(n\)和\(k\)。

输出格式

输出一行一个整数表示答案。

数据规模与约定

• 对于\(30%\)的数据，保证 \(n, k \leq 10^3\)。
• 对于\(60%\)的数据，保证 \(n, k \leq 10^6\)。
• 对于\(100%\)的数据，保证 \(1 \leq n, k \leq 10^9\)。

整理&思路

这道题的常规暴力思路就是：

for(int i=1;i<=n;i++)sum+=k%i;

但是很明显，这道题没有这么简单。首先就是精度的问题，其次就是时间的问题——这样的O(n)太慢了。
这时候我们就可以利用这样的神秘小定理：
首先 \(a \bmod b = a - b * \lfloor \frac{a}{b} \rfloor\)，所以我们就可以得到这样的东西：

\[ans = \sum_{i=1}^{n} k - i * \lfloor \frac{k}{i} \rfloor = n * k - \sum_{i-1}^{n} i * \lfloor \frac{k}{i} \rfloor \]

显然， \(\lfloor \frac{k}{i} \rfloor\)大约有\(\sqrt{k}\)种取值，所以就可以得到下面的代码，复杂度\(O(\sqrt{k})\)

#include<bits/stdc++.h>
#define int long long
using namespace std;int n, k;signed main() {scanf("%lld%lld",&n,&k);int sum=0;for(int l=1,r,t;l<=n;l=r+1)r=(t=k/l) ? min(k/t,n) : n,sum-=t*(r-l+1)*(l+r)>>1;printf("%lld",sum+n*k);return 0;
}

恭喜AC!