【BZOJ1031】字符加密
【BZOJ4198】荷马史诗

【BZOJ1257】余数之和

Zarxdy34 posted @ 2015年12月01日 20:11 in BZOJ with tags 数论 , 325 阅读

    k/i的商只有sqrt(k)个,并且如果k div i == k div (i+1) == k div (i+2) == ... == k div j,那么k mod i , k mod (i+1) , k mod (i+2) , ... , k mod j是一个等差数列。

 

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

LL n,k,ans;

int main()
{
	scanf("%lld%lld",&n,&k);
	for (LL l=1,r=1;l<=n;l++)
	{
		LL c=k/l,p=k-c*l,wl,wr;
		if (c==0) r=n,wl=p,wr=p;
			else r=min(n,l+p/c),wl=p,wr=p-c*(r-l);
		ans+=(wl+wr)*(r-l+1)/2;
		l=r;
	}
	printf("%lld\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter