目录
BZOJ1257 余数之和题解ｃｏｄｅ
BZOJ1257 余数之和
题目传送门
题解
有点妙的一题。首先我们需要求的东西是\(\sum_{i=1}^{n}k\%i\)，然后我们可以对这个公式进行一下转化：\(\sum_{i=1}^{n}(k-(k/i)*i)\)，这个还是比较好意会出来的。然后我们把这个公式拆一下：\(\sum_{i=1}^{n}k-\sum_{i=1}^{n}i*(k/i)=n*k-\sum_{i=1}^{n}i*(k/i)\)。这样前面就是一个定值了，而后面那部分由于\(k/i\)在一定的范围内是不变的，所以我们只需要把这些相同的部分放在一起算就行了。可以证明出来这些不同的取值只有根号个。所以这是有一点类似于分块的方法。至于大于\(k\)的那么取模，就直接加上个数乘以\(k\)就行了。
ｃｏｄｅ
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
#define PAUSE printf("Press Enter key to continue..."); fgetc(stdin);
ll ans,n,k;
/*==================Define Area================*/
int main() {
read(n);read(k);
ans=n*k;
for(ll l=1,r=0;l<=n;l=r+1){
if(k/l)r=min(n,k/(k/l));
else r=n;
ans-=(k/l)*(r-l+1)*(l+r)>>1;
}
printf("%lld\n",ans);
return 0;
}
转载于:https://www.cnblogs.com/Apocrypha/p/9443624.html
相关资源：JAVA上百实例源码以及开源项目
