题目描述
?
给你两个数n，k，请求出
的值。
-
输入每行两个数n, k(1 <= n, k <= 10^9).输出输出和，每个结果占一行。样例输入
5 4 5 3
样例输出5 7
题目分析:
对于此题不能直接进行暴力，数值大，只能用sqrt(n)的算法，首先计算n%i的余数和，i=1~n；注意到：n%i=n/i*i;
因此我们可以模拟从i=1~sqrt(n);sum+=n%i;对于i对应的j=n/i，可以知道(n/i~n/i+1)==d；对与这组数，计算得到
s1=((n/i-n/(i+1))*n)-d*(n/(i+1)+1+......+n/i)；sum+=s1;直到循环结束，就得到n%i的余数和，我们用ModSum(n)。
现在我们求k%i的余数和，i=1~n；进行分析k和n即可，
一、k
k时，k%n==k 二、k=n res=ModSum(k)
三、k>n res=ModSum(k); { for(int i=n+1;i<=n;i++)
res-=k%i;//减去多计算的值即可。
}
?
AC代码：
?
/** *1、ModSum1()：O(n) *2、ModSum2()：O(sqrt(n)) *1 2 3 4 *16 8 5 4 * 1 2 3 */ #include#include #include