P2261 [CQOI2007]余数求和

题意还是很清晰，很容易理解

1e9范围明显不能暴力，除非你能把常数优化到\(\frac1 {10}\)，但我实在想象不到用了这么多取模怎么把常数优化下去

我们可以把\(k\%i\)变成\(k-k/i*i\)(整除)

那么总的和也就从\(\sum_{i=1}^{n}k\%i\)变成了\(\sum_{i=1}^n k-k/i*i\)，又可以转化为\(nk-\sum_{i=1}^n k/i*i\)

\(k/i\)的值只有有\(\sqrt k\)种，且相同的值都是连续出现的，所以我们可以直接利用等差数列求\(\sum_{i=1}^n k/i*i\)

下面放代码吧

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cctype>

#define ll long long

#define gc getchar

using namespace std;

inline ll read(){

	ll a=0;int f=0;char p=gc();

	while(!isdigit(p)){f|=p=='-';p=gc();}

	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}

	return f?-a:a;

}ll n,k,ans;

int main(){

	n=read();k=read();

	for(int l=1,r;l<=n;l=r+1){

		if(k/l)r=min(k/(k/l),n);

		else r=n;

		ans+=k/l*(r-l+1)*(l+r)/2;

	}

	ans=n*k-ans;

	printf("%lld\n",ans);

	return 0;

}

不要抄袭哦

巴特西

P2261 [CQOI2007]余数求和

最新文章

热门文章