题目描述

?

给你两个数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