Description
给出正整数n和k,计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值,其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7
Input
输入仅一行,包含两个整数n, k。
Output
输出仅一行,即j(n, k)。
Sample Input
Sample Output
HINT
50%的数据满足:1<=n, k<=1000 100%的数据满足:1<=n ,k<=10^9
题解
首先,若$k<n$,那么把答案加上$(n-k)*k$,然后n=k;
由于$kmod i = k - leftlfloorfrac k i ight floor * i$,而有些$leftlfloorfrac k i ight floor$是相同的,可以一起计算,
即,若$leftlfloorfrac k a ight floor = leftlfloorfrac k b ight floor (a leq b)$
那么$[a,b]$对答案的贡献是$k*(b-a) + leftlfloorfrac k a ight floor * frac{(a+b)(b-a+1)}2$。
又因为对于某个数s,若存在$i$使得$leftlfloorfrac k i ight floor = s$,那么最大的满足条件的$i$为$leftlfloorfrac k s ight floor$,所以上述$[a,b]$的右端点$b$是可以确定的。
又因为$leftlfloorfrac k i ight floor$只有$O(sqrt{k})$种($i leq sqrt{k}$时,只有$O(sqrt{k})$个$i$;$i > sqrt{k}$时,只有$O(sqrt{k})$个$leftlfloorfrac k i ight floor$),所以复杂度为$O(sqrt{k})$。
附代码:
#include <cstdio> typedef long long LL; inline LL get(LL t) { return t * (t + 1) / 2; } int main() { LL n, k; scanf("%lld%lld", &n, &k); LL ans = k * n; if (n > k) n = k; for (LL i = 1, end; i <= n; i = end + 1) { end = k / (k / i); if (end > n) end = n; ans -= k / i * (get(end) - get(i - 1)); } printf("%lld ", ans); return 0; }