洛谷 P2261 [CQOI2007]余数求和

一看就知道是一个数学题。嘿嘿～

讲讲各种分的做法吧。

30分做法：不知道，这大概是这题的难点吧！

60分做法：

一是直接暴力，看下代码吧～

#include <bits/stdc++.h>

using namespace std;

typedef int _int;

#define int long long

_int main()

{

    int n,k,ans=0;

    cin>>n>>k;

    for (int i=1;i<=n;++i) {

        ans+=(k%i);

    }

    cout<<ans;

    return 0;

}

第二种做法非常接近正解。

首先显然\(k~mod~i=k-\lfloor \frac{k}{i} \rfloor*i\)。

所以我们马上一波转化，\(\sum_{i=1}^{n}k~mod~i=n*k-\sum_{i=1}^{n}\lfloor \frac{k}{i} \rfloor*i\)。

那么这一截\(\sum_{i=1}^{n}\lfloor \frac{k}{i} \rfloor*i\)怎么求呢？

这个时候，直觉会告诉我们，\(\lfloor \frac{k}{i} \rfloor*i\)很有问题。

因为是向下取整，所以会有许多\(\lfloor \frac{k}{i} \rfloor\)是一样的。于是就会有一个一个的区间。

对于每个这样的区间，在乘一个\(i\)后，显然是一个等差数列。

不信看这个：

\((int)8/3=(int)8/4=2~~~~=>~~~~8/3*3+2=8/4*4\)

所以我们可以枚举\(i\)，对于每一个\(i\)，求出\(t=k/i\)，

令\(l=i,r=min(n,k)\)二分，如果\(mid/i=t，l\)扩大，否则\(r\)缩小。

找到后直接等差数列求和。

最后使\(i=r+1\)。这样表面时间复杂度是\(O(\sqrt{n}*log(n))\)。

实则不然，因为我们的\(i\)跳跃的距离基本上很小很小，所以这代码比\(O(n)\)还慢！

看下代码吧！

#include <bits/stdc++.h>

using namespace std;

typedef int _int;

#define int long long

int n,k,ans;

_int main()

{

    cin>>n>>k;

    ans=n*k;

    for (int i=1;i<=min(n,k);++i) {

        int l=i,r=min(n,k),t=k/i,j=i;

        while (l<=r) {

            int mid=(l+r)/2;

            if (mid/i==t) l=mid+1,j=mid;

            else r=mid-1;

        }

        int a1=t*i,an=a1+(j-i)*t,g=j-i+1;

        ans-=(g*(a1+an)/2);

        i=j;

    }

    cout<<ans;

    return 0;

}

100正解：

有了上面第二个60分做法的思路，正解就不言而喻了。

只要把\(log(n)\)找区间改成\(O(1)\)就好了。

具体怎么改呢？

我们同样的枚举\(i\)，假设区间为\([l,r]\)，那么\(l=i\)显然，然后就剩\(r\)有点难搞了。

想想，我们每一段的公差都是\(\lfloor \frac{k}{i} \rfloor\)，那么显然当\(k~mod~i=0\)时，\(r\)截止。

所以，\(r=k/(k/l)\)。

那么，就完结了，上代码！真正的极简AC难懂～

#include <bits/stdc++.h>

using namespace std;

typedef int _int;

#define int long long

int n,k,ans;

_int main()

{

    cin>>n>>k;

    ans=n*k;

    for (int i=1;i<n;++i) {

        int l=i,t=k/l,r=t?min(n,k/t):n;

        int a1=t*l,an=a1+(r-l)*t,g=r-l+1;

        ans-=(g*(a1+an)/2);

        i=r;

    }

    cout<<ans;

    return 0;

}

巴特西

洛谷 P2261 [CQOI2007]余数求和

最新文章

热门文章