题解 UVA1363 【约瑟夫的数论问题 Joseph's Problem】

· · 题解

提醒，双倍经验

此题与P2261 [CQOI2007]余数求和，完全一样，可尝试用本题代码去提交此题代码。

解题思路（进入正题）

打过高精取模的都知道，

\sum\limits^n_{i=1}k \bmod i=n\times k-\sum\limits^n_{i=1}i\times \lfloor \frac{k}{i}\rfloor

然后用整除分块解决就好了。

注意本组有多组数据。

那么整除分块该怎么用呢？

About 整除分块

（学好整除分块对以后学数论很有帮助）

首先，整除分块的形式，就像这道题一样:

\sum\limits^n_{i=1} \lfloor \frac{n}{i}\rfloor

我们可以通过打表或其他方式发现，

有许多 \lfloor \frac{n}{i}\rfloor 是一样的，并以块状分布。

对于每一个值相同的块，它的最后一个数就是 n/(n/i)

然后我们就可以处理了。

时间复杂度为 O(\sqrt{n})

下面放上 AC 代码。

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,k,ans;
int main(){
    while(~scanf("%lld%lld",&n,&k)){
        ans=n*k;
        for(ll l=1,r=0;l<=n;l=r+1){
            if(k/l!=0) r=min(k/(k/l),n); 
            else r=n;
            ans-=(k/l)*(r-l+1)*(l+r)/2;
        }
        printf("%lld\n",ans);
    }
}