CodeForces - 616E
Sum of Remainders
|
Time Limit: 2000MS |
|
Memory Limit: 262144KB |
|
64bit IO Format: %I64d & %I64u |
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
Input
3 4
Output
4
Input
4 4
Output
1
Input
1 1
Output
0
Source
Educational Codeforces Round 5
//题意就不说了，直接上大神的思路了，很6的方法
题意：求解
∑ m i=1 nmodi
。
思路：我们化简
nmodi=n−n/i∗i
。
这样原式
=n∗m−∑ m i=1 (n/i∗i)
首先
m<=n √
时，直接暴力，对于剩下的，我们可以分块来搞，总会存在一段连续的值使得
n/i
为定值，那么我们找到这个区间就可以了。不过貌似在除以2的时候，会出问题，我直接上逆元就过了。
#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;
}
|