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; } }