【BZOJ 1257】 [CQOI2007]余数之和sum

1257: [CQOI2007]余数之和sumTime Limit:5 SecMemory Limit:162 MBSubmit:2081Solved:969[Submit][Status]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

5 3

Sample Output

7

HINT

50%的数据满足：1<=n, k<=1000 100%的数据满足：1<=n ,k<=10^9

Source

数论

可以发现k/i的值只有sqrt(k)个，而k/i相同的连续几个i的k%i的值呈等差数列，因此可以O(1)算出，最终的复杂度就是O(sqrt(k))。

#include <iostream>#include <cstdio>#include <cmath>#include <cstring>#include <algorithm>#define LL long longusing namespace std;int main(){int n,k;scanf("%d%d",&n,&k);int now=2;LL ans=0LL;while (now<=min(n,k)){int d=k/now;int x=k/d;int a=k%now+k%x,b=x-now+1;ans=ans+((LL)a*b)/2LL;a=k%x+k%(min(n,k)+1),b=x-min(n,k);if (x>min(n,k)) ans=ans-((LL)a*b)/2LL;now=x+1;}if (n>k)ans=ans+((LL)(n-k)*k);cout<<ans<<endl;return 0;}

感悟：

1.一开始WA了好几次，因为等差数列求和公式写错；没有及时转化long long

2.在莫比乌斯函数的题目中也用到了这个技巧：商相同的一起算

爱情纯属天性，不用思考。你不能为爱而爱，