BZOJ 1257: [CQOI2007]余数之和sum

starli posted @ 2016年2月11日 09:42 in 数学 , 248 阅读

注意一个性质 k%n=k-k/(k/n)

于是可以化简成n*k-(k/i)*i  (1<=i<=min(n,k))

只要枚举k/i就可以了,令枚举的这个k/i为t

每一个满足 k/i=t的都在一个区间里

在这里说一下枚举的方法 这个方法复杂度是$\sqrt{n}$

for(int a=1;a<=min(n,k);a= k/(k/a)+1){
	//todo 两个a之间就是对应k/i= k/a 的区间
}

代码如下

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
LL n,k,ans,t;
LL min(LL a,LL b){return a<b?a:b;}
int main(){
	// freopen("1257.in","r",stdin);freopen("1257.out","w",stdout);
	scanf("%lld%lld",&n,&k);
	for(t=1;t<=min(n,k);t=k/(k/t)+1){
		LL nxt=min(k/(k/t),n);
		nxt=min(nxt,k);
		ans+=(k/t)*(t+ nxt )*(nxt-t+1)/2;
	}
	ans=n*k-ans;
	printf("%lld",ans);
	return 0;
}
for(int a=1;a<=min(n,k);a= k/(k/a)+1){
	//todo
}

登录 *


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