Submit?Status
Description
Calculate the value of the sum:?nmod1?+?nmod2?+?nmod3?+ … +?nmodm. As the result can be very large,you should print the value modulo?109?+?7?(the remainder when divided by?109?+?7).
The modulo operator?amodb?stands for the remainder after dividing?a?by?b. For example?10mod3?=?1.
Input
The only line contains two integers?n,?m?(1?≤?n,?m?≤?1013) — the parameters of the sum.
Output
Print integer?s?— the value of the required sum modulo?109?+?7.
Sample Input
3 4
4
4 4
1
1 1
0
Source
Educational Codeforces Round 5
//题意就不说了，直接上大神的思路了，很6的方法
题意：求解
思路：我们化简
这样原式
首先
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<algorithm>
#define IN __int64
#define M 1000000007
using namespace std;
IN kp(IN a,IN n)
{
IN ans = 1;
while(n)
{
if(n&1)
ans=ans*a%M;
a=a*a%M;
n>>=1;
}
return ans;
}
int main()
{
IN n,m,sum,ans1,i,j,nn;
while(scanf("%I64d%I64d",&n,&m)!=EOF)
{
sum=n%M*(m%M)%M;
nn=sqrt(n);
ans1=0;
for(i=1;i<=min(m,nn);i++)
ans1=(ans1+n/i%M*i%M)%M;
if(m>nn)
{
if(nn*nn==n)
nn--;
for(i=1;i<=nn;i++)
{
IN r=min(m,n/i);
IN l=n/(i+1)+1;
if(l>r||r<=nn)
continue;
ans1=(ans1+(l+r)%M*((r-l+1)%M)%M*kp(2,M-2)%M*i%M)%M;
}
}
printf("%I64d\n",(sum-ans1+M)%M);
}
return 0;
}
