CodeFroces--Joseph’s Problem

 

题目意思:给出n k 求  k%1 + k%2 +k%3+...+k%n 的和

利用分块的思想 我们知道 k%i ==k-k/i*i 

同时 一段连续的区间的 k/i 是相等的

#include<bits/stdc++.h>
using namespace std;
#define maxn
#define LL long long
int main(){
 // freopen("joseph.in","r",stdin);
 // freopen("joseph.out","w",stdout);
  LL n,k;
  cin>>n>>k;
  LL ans=0;
  if(n>=k){
     ans+=k*(n-k);
     for(LL l=1,r=0;l<=k&&r<=k;l=r+1){
        r=k/(k/l);
        LL len=r-l+1;
        ans+=len*k-(l+r)*len/2*(k/l);
     }
     cout<<ans<<endl;
  }else{
     ans=0;
     for(LL l=1,r=0;l<=k;l=r+1){
        r=k/(k/l);
        if(r>n) r=n;
        LL len=r-l+1;
        ans+=len*k-(l+r)*len/2*(k/l);
        if(r==n) break;
     }
     cout<<ans<<endl;
  }
}

 

全部评论

相关推荐

03-14 18:30
华侨大学 Java
牛客20485985...:没关系的吧,我也是双飞大二,有过很多约面。海投呗,我觉得介意大二的不是很多。你的项目没毛病。建议看一看agent
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务