BZOJ1257 [CQOI2007]余数之和[规律]

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

被zcr和yy轮流嘲讽了一番，感觉自己智商日渐下降。。。\TヘTツ

先拆mod变成整数除法，然后就是$nk- \Sigma_{i=1}^{n} i * \lfloor \frac{k}{i} \rfloor$。求后面那个。

然后发现$\lfloor \frac{k}{i} \rfloor$是连续且单调不增的。对于$x$，$[x,\lfloor \frac{k}{\lfloor \frac{k}{i} \rfloor} \rfloor]$内这个商是一样的。可以意会。

这个是找规律得到的，不会证QWQ。于是每一小段一样的商乘以这一段的每一个$i$累加。

复杂度是在$i \leq \sqrt{k}$时有$\sqrt{k}$种商。$i \geq \sqrt{k}$时的商小于$\sqrt{k}$，也最多$\sqrt{k}$种。于是复杂度是根号的。

WA：关于longlong的事以及每次区间右端点要判是否超过$n$。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 inline ll sum(ll i,ll j){return (i+j)*(j-i+)/;}

 ll ans,n,k;

 int main(){//freopen("test.in","r",stdin);//freopen("test.out","w",stdout);

     read(n),read(k);ans=n*k;(n>k)&&(n=k);

     for(register ll i=,r=;i<=n;i=r+)ans-=sum(i,r=_min(n,k/(k/i)))*(k/i);

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

 }