CodeForces - 616E Sum of Remainders （数论）大数取余求和 好
|
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
44 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("%I64dn",(sum-ans1+M)%M);
}
return 0;
}
|
（编辑：银川站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
