题解 P2424 【约数和】

zzlzk · 2017-09-22 19:12:58 · 题解

• 把f(x)用数学方式表示一下就是f(x)=\sum\limits_{d|x}d

• 那 ans=\sum\limits_{i=x}^{y}f(i)=\sum\limits_{i=x}^{y}\sum\limits_{d|i}d

• 那我们就可以直接枚举然后累加就可以了。

• 但这样的时间复杂度是O(\sum\limits_{i=x}^{y}\sqrt i)，会TLE

• 所以换一种思路，枚举约数

• 考虑1-n中有几个数是 d 的倍数

• 假如1-n中存在 d 的倍数，那这个数肯定可以表示为 k·d(k\in N_+)

• k$ 的范围可以再简化一下，$1\leq k·d\leq n\Rightarrow 1 \leq k \leq \lfloor\frac{n}{d}\rfloor

• 也就是说从1-n 中把 d 的倍数单独拿出来，那就是d,2d,3d.....\lfloor\frac{n}{d}\rfloor d

• 所以1-n中 d 的倍数的个数就是 \lfloor\frac{n}{d}\rfloor

• 求出 y 的个数，再减去 x-1 的个数，也就是x-y 的个数，这个是比较好想的，所以我就不详细说了。

• 这样\sum\limits_{i=1}^{n}f(i)就可以表示为\sum\limits_{i=1}^{n}(\lfloor\frac{n}{i}\rfloor*i)

• 那ans=\sum\limits_{i=1}^{y}(\lfloor\frac{y}{i}\rfloor*i)-\sum\limits_{i=1}^{x-1}(\lfloor\frac{x-1}{i}\rfloor*i)

• 这种做法时间复杂度是O(y)，还是会TLE

• 再看\sum\limits_{i=1}^{n}(\lfloor\frac{n}{i}\rfloor*i)

• 只看\lfloor\frac{n}{i}\rfloor，胡乱找个数列出来\lfloor\frac{n}{i}\rfloor(1\leq i \leq n)的值

• 以12为例，列出来是12,6,4,3,2,2,1,1,1,1,1,1 ，第 i 个数表示\lfloor\frac{n}{i}\rfloor的值

• 发现这里面有些数是重复的，考虑能不能把这些重复的一次算出来

• 把那些相同的值用区间来表示，那只要求出左右端点l,r来就好了

• l$ 比较好求，观察上面的数列，$l$ 就是上一个$r$加$1$，初始$l=1

• 那 r 怎么求呢？其实很简单

• r=n/(n/l)

• 约数=n/l

• 约数的个数=\sum\limits_{i=l}^r i，用等差数列求和公式表示一下就是(l+r)*(r-l+1)/2

• 即ans+=(n/l)*(l+r)*(r-l+1)/2

• 然后就愉快的AC啦！

比题解不知道短到那里去的代码

#include<cstdio>
using namespace std;
typedef long long ll;

ll sum(int n) {
    if(n<=1) return n;
    ll ans=0;
    for(ll l=1,r;l<=n;l=r+1) {
        r=n/(n/l);
        ans+=(n/l)*(l+r)*(r-l+1)/2;
    }
    return ans;
}

int main() {
    int x,y;
    scanf("%d%d",&x,&y);
    printf("%lld\n",sum(y)-sum(x-1));
    return 0;
}