UVALive - 3521 Joseph's Problem (整除分块)

给定$n,k$$(1\leqslant n,k\leqslant 10^9)$，计算$\sum\limits _{i=1}^nk\: mod\:i$

通过观察易发现$k\%i=k-\left \lfloor \frac{k}{i} \right \rfloor*i$，因此我们考虑把$\left \lfloor \frac{k}{i} \right \rfloor$的值相同的$i$分成一组直接求和，复杂度为$O(\sqrt{n})$。

整除分块原理（选自某dalao博客）

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 ll n,k;

 int main() {

     while(scanf("%lld%lld",&n,&k)==) {

         ll ans=;

         for(ll l=,r; l<=n; l=r+) {

             ll t=k/l;

             r=t&&k/t<n?k/t:n;

             ans+=k*(r-l+)-t*((l+r)*(r-l+)/);

         }

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

     }

     return ;

 }

巴特西

UVALive - 3521 Joseph's Problem (整除分块)

最新文章

热门文章