目录

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 
    
     using namespace std;typedef long long ll;bool Finish_read;template
     
      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
      
       inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}template
       
        inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('\n');}template
        
         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;}