[CQOI2007]余数之和sum

Time Limit:5000MS Memory Limit:165536K
Total Submit:41 Accepted:17
Case Time Limit:1000MS

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

Source
额。。k mod i=k-(k/i)*i。。。
那么对于一段k/i相等的可以一起计算。。
可以证明最多分成sqrt（n）段。。
Code：

#include <iostream>using namespace std;typedef long long ll;int main(){ int n,k;cin>>n>>k;ll ans=0; for(int i=1;i<=n;i++) { int a=k/i,l=k/(a+1)+1,r=a?k/a:n; if(r>=n)r=n; ans+=ll(k)*(r-l+1)-ll(a)*(l+r)*(r-l+1)/2; i=r; } cout<<ans<<endl;}75 3