频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
Sum of Remainders思路及解题方法
2018-08-10 13:51:02           
收藏   我要投稿

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 1e9+7 (the remainder when pided by 1e9+7).

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

Input

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

Output

Print integer s — the value of the required sum modulo 1e9+7.

Examples

Input1

3 4

Output1

4

Input2

4 4

Output2

1

Input3

1 1

Output3

0

题目大意

给出n和m两个正整数(1<=n,m<=10^13),求:
ans=n%1+n%2+n%3+…….n%m

思路

由于n,m都是十分大的整数,则从1枚举到m,再一直 ans+=n%i的算法很明显过不了(TLE)。
由于涉及到mod运算且范围如此的大,我们可以尝试着去找规律。
这里写图片描述
这里写图片描述
这里写图片描述
上图中,n分别%每列数的余数在每列中都构成了一列等差数列。
这是为什么呢?我们设i为我们一直在枚举的数。
则有: n=k*i+p; p=n%i;<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPjxiciAvPg0KPHN0cm9uZz62+Mv509C1xHDWrrrNvLTOqs7Sw8fSqsfzs/a1xLarzvehozwvc3Ryb25nPjxiciAvPg0KPHN0cm9uZz61sXAmZ3Q7PWvKsaOs1PLT0G49KGkrMSkqaytwLWs7PC9zdHJvbmc+PGJyIC8+DQq0y8qxo6zO0sPHyeggaTI9KGkrMSkscDI9KHAtayk7PGJyIC8+DQq/ydLUt6LP1qOsyPRwJmd0Oz1rLGm1xNa1vs2/ydLU0rvWsbXdz8LIpaGjPGJyIC8+DQprsrux5Mqxo6xwtcTWtb7NubmzydK7uPa1yLLuyv3B0KGjPGJyIC8+DQphbnPDv7TOvs2807XI09pTdW1wo6y2+GnDv7TOseO/ydLUvNO1yNPayv3B0LOktsihozwvcD4NCjxoMSBpZD0="代码">代码

#include
#include
using namespace std;
#define ll long long
const ll MOD=(1e9+7);
ll n,m,ans,i=1;
int main(){
 scanf("%lld%lld",&n,&m);
 if(m>n)ans=((m-n)%MOD*(n%MOD))%MOD,m=n;
 while(im+1){//多算了(m+1)至i
  i--;
  ll k=n/i,p=n%(m+1),lp=n%i;
  ll d=(p-lp+k)/k,x=(p+lp);
  if(d%2==0)d/=2;
  else if(x%2==0)x/=2;
  ans=(ans-((x%MOD)*(d%MOD))%MOD+MOD)%MOD;
 }
 if(i==m)//少算了m
  ans=(ans+(n%m)%MOD)%MOD;
 printf("%lld\n",ans);
}

/*
56598 56
*/
点击复制链接 与好友分享!回本站首页
上一篇: 断路器聚合监控Hystrix Turbine
下一篇:服务消费者rest和ribbon
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站