【题目描述】 给出正整数n和k(1<=n,k<=10^9)，计算k mod 1+k mod 2+k mod 3+…+k mod n的值。 【输入格式】 两个整数n,k 【输出格式】 计算结果 【样例输入】 5 3 【样例输出】 7 【分析】 被除数固定，除数逐次加1，直觉上余数也应该有规律。设p=k div i，因k/(i+1)和k/i差别不大，如果k div (i+1)也等于p，则k mod (i+1)=k-(i+1)*p=k-i*p-p=k mod i-p。这样可以在枚举i时计算结果了。
#include<iostream> #include<algorithm> using namespace std; long long sum(int a, int d, int n) { return (long long)(2*a-n*d)*(n+1)/2; } int main() { int n, k; while(cin >> n >> k) { int i = 1; long long ans = 0; while(i <= n) { int q = k % i, p = k / i; int cnt = n - i; if(p > 0) cnt = min(cnt, q / p); ans += sum(q, p, cnt); i += cnt + 1; } cout << ans << "\n"; } return 0; }转载于:https://www.cnblogs.com/JRX2015U43/p/6533523.html
