F - Sum of Remainders

Time Limit:2000MS Memory Limit:262144KB 64bit IO Format:%I64d & %I64u

Description

Calculate the value of the sum: n mod 1 + n mod 2 + n mod 3 + ... + n mod m. As the result can be very large, you should print the value modulo 10⁹ + 7 (the remainder when divided by 10⁹ + 7).

The modulo operator a mod b stands for the remainder after dividing a by b. For example 10 mod 3 = 1.

Input

The only line contains two integers n, m (1 ≤ n, m ≤ 10¹³) — the parameters of the sum.

Output

Print integer s — the value of the required sum modulo 10⁹ + 7.

Sample Input

Input

3 4

Output

Input

4 4

Output

Input

1 1

Output

//给你两个数n,m，问你n % 1 + n % 2 + … + n% m为几

这个题目的思路是，和为 n * m - sum ( [ n / i ] * i ) ，[ ] 是向下取整，i 从(1--- m)

具体是:

前面的 n*m 肯定就这样了

主要是后面的 :将 [ n / i ] 相同的做一个区间，用求和公式去节省时间

i 从 1 --- sqrt (n) ;

l = n / ( i + 1 ) + 1 , r = n / i ; // 这就是一个个的区间

比如 n = 20 , m = 20

i=1 --> l=11, r=20 n / (11---20) 都是等于 1

i=2 --> l=7, r=10 n / (7---10) 都等于2

i=3 --> l=r=6

i=4 --> l=r=5

注意一些特殊情况，看注释

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 using namespace std;

 #define ll __int64

 const ll MOD=1e9+;

 int main()

 {

     ll n,m;

     scanf("%I64d%I64d",&n,&m);

     ll ans=(n%MOD)*(m%MOD)%MOD;

     ll temp=,las=m+;//记录哪些数没被减

     m=min(n,m);//n 余大于 n 的都等于 n

     ll nn=(ll)sqrt(n*1.0);

     for (ll i=;i<=nn;i++)

     {

         ll l = n/(i+)+;

         ll r = n/i;

         r=min(r,m);//可能 r 比 m 大

         if (l>r) continue;

         las=min(las,l);

         ll s1=l+r , s2 =(r-l+);//这里高斯求和有个坑，要先判断哪个数可以除2，再乘

         if (s1%==) s1/=;     //直接用公式也不对，会超出ll限制

         else s2/=;

         s1%=MOD;s2%=MOD;

         s1=(s1*s2)%MOD;

         s1=s1*i%MOD;

         temp=(temp+s1)%MOD;

     }

     ans=(ans+MOD-temp)%MOD;

     for (ll i=;i<las;i++) //剩下的没被减得数，将n余之为0的最大整数减去

     {

         temp=n/i%MOD*i%MOD;

         ans=(ans+MOD-temp)%MOD;

     }

     printf("%I64d\n",ans);

     return ;

 }

巴特西

Sum of Remainders(数学题)

F - Sum of Remainders

最新文章

热门文章