CodeForces - 616E Sum of Remainders （数论）大数取余求和 好

3 4

Output

4

4 4 1 1 1 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;
}