【二次爆炸记·第二弹】（欧拉筛法求约数和）Savrsen

分手后的思念是犯贱 2021-11-24 00:06 236阅读 0赞

### 文章目录 ###

*  题目
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例
     *   *  样例输入1
         *  样例输出1
         *  样例输入2
         *  样例输出2
 *  解析
 *   *  欧拉筛法
     *   *  筛约数和
     *  Code
 *  后记

--------------------

# 题目 #

## 题目描述 ##

如果一个数等于它的所有因数（小于自身的）之和，那么这个数就是完美的。例如，28是完美的，因为 28 = 1 + 2 + 4 + 7 + 14 28=1+2+4+7+14 28=1\+2\+4\+7\+14。

基于这个定义，我们数字n的不完美度定为 f （ n ） f（n） f（n），它等于n与n的所有因数（小于n的）之和的差的绝对值，因此完美数的不完全度为 0 0 0，其余自然数的不完全度都大于 0 0 0。

例如：

● f （ 6 ） = ∣ 6 − （ 1 + 2 + 3 ） ∣ = 0 f（6）=|6-（1+2+3）|=0 f（6）=∣6−（1\+2\+3）∣=0

● f （ 11 ） = ∣ 11 − （ 1 ） ∣ = 10 f（11）=|11-（1）|=10 f（11）=∣11−（1）∣=10

● f （ 24 ） = ∣ 24 − （ 1 + 2 + 3 + 4 + 6 + 8 + 12 ） ∣ = ∣ − 12 ∣ = 12 f（24）=|24-（1+2+3+4+6+8+12）|=|-12|=12 f（24）=∣24−（1\+2\+3\+4\+6\+8\+12）∣=∣−12∣=12

写一个程序，对于正整数A和B，计算A和B之间所有数字的不完美度之和：即 f （ A ） + f （ A + 1 ） + … + f （ B ） f（A）+f（A+1）+…+f（B） f（A）\+f（A\+1）\+…\+f（B）。

## 输入格式 ##

第一行输入包含两个整数 A A A和 B B B（ 1 ≤ A ≤ B ≤ 1 e 7 1≤A≤B≤1e7 1≤A≤B≤1e7）。表示题目中的 A A A和 B B B。

## 输出格式 ##

输出一个整数。表示 f （ A ） + f （ A + 1 ） + … + f （ B ） f（A）+f（A+1）+…+f（B） f（A）\+f（A\+1）\+…\+f（B）。

## 样例 ##

### 样例输入1 ###

1 9

### 样例输出1 ###

### 样例输入2 ###

24 24

### 样例输出2 ###

# 解析 #

第一眼看上去，既然是数轮题，那么首先想到的就应该是 背到的模板 欧拉。

为什么这么说，因为欧拉在数论领域中真心无处不在，图论也有他的一席之地。。。

因此这道题我们手推一下即可发现，这应该是*欧拉筛求约数和* 的板了吧。。。

## 欧拉筛法 ##

筛法就是能够快速筛出素数的一种方法，而欧拉筛法则是埃氏筛法的改良版。

因为埃氏筛法并不是线性的筛素数，有些合数可能会被不同的素数筛出去多遍，还可以更加高效，所以欧拉筛法“取长补短”，复杂度也从 O ( n l o g l o g n ) O(n loglogn) O(nloglogn)变成 O ( n ) O(n) O(n)。。。

当然，它的核心思想就是**让所有的合数被他的最小质因子给筛出去**，以后就可以不用再被筛一次了。而他的线性筛法，也正是因为这样才得以进行的。

贴板真好用

int prim[N + 5], cnt;
    bool vis[N + 5];
    
    void prime (int n){ 
    	for (int i = 2; i <= n; i++){ 
    		if (!vis[i]) prim[++cnt] = i;
    		for (int j = 1; j <= cnt && prim[j] * i <= n; j++){ 
    			vis[i * prim[j]] = 1;
    			if (i % prim[j] == 0) break;
    		}
    	}
    }

注意看上面的j循环，不知道有没有童鞋疑惑为什么不管是不是质数都要枚举这层循环，但是仔细看变量，j实质上是在充当下标使用，让每个i都能乘上所有的prim，把利用素数筛合数的思路放大到最大化。当然这并不代表我不懂哈 强力辩解ing

还有一点也困扰了我很久，为什么当 i % p r i m \[ j \] = = 0 i \\% prim\[j\] == 0 i%prim\[j\]==0时就退出？请大家思考几分钟哈（注意结合欧筛的核心思想）~~~

--------------------

OK，欧筛的核心思想是让**合数被他的最小质因子给筛出去**，因此，当 i % p r i m \[ j \] = = 0 i \\% prim\[j\] == 0 i%prim\[j\]==0时， i = p r i m \[ j \] ∗ x i = prim\[j\] \* x i=prim\[j\]∗x， x x x是任意正整数。到后面prim数组又添加了新元素后，prim数组中的元素始终是严格递增的，设到后面新添了一个素数 p r i m \[ k \] prim\[k\] prim\[k\]，就要筛去 i ∗ p r i m \[ k \] i \* prim\[k\] i∗prim\[k\]，可是 i ∗ p r i m \[ k \] = x ∗ p r i m \[ j \] ∗ p r i m \[ k \] i \* prim\[k\] = x \* prim\[j\] \* prim\[k\] i∗prim\[k\]=x∗prim\[j\]∗prim\[k\]，也就是说这个乘积的最小质因子是 p r i m \[ j \] prim\[j\] prim\[j\]，但在这里却又重新筛了一遍，这不符合欧拉筛的线性特征，因此的证。

### 筛约数和 ###

首先我们得先了解一下约数和的概念，一个正整数n的约数和，我们记为 s ( n ) s(n) s(n)，那么 s ( n ) = ( 1 + p 1 1 + p 1 2 + … + p 1 w 1 ) ( 1 + p 2 1 + p 2 2 + … + p 2 w 2 ) ( 1 + p 3 1 + p 3 2 + … + p 3 w 3 ) … ( 1 + p m 1 + p m 2 + … + p m w m ) s(n) = (1 + p\_1^1 + p\_1^2 + …+ p\_1^\{w\_1\})(1 + p\_2^1 + p\_2^2 + … + p\_2^\{w\_2\})(1 + p\_3^1 + p\_3^2 + … +p\_3^\{w\_3\})…(1 + p\_m^1 + p\_m^2 + … + p\_m^\{w\_m\}) s(n)=(1\+p11\+p12\+…\+p1w1)(1\+p21\+p22\+…\+p2w2)(1\+p31\+p32\+…\+p3w3)…(1\+pm1\+pm2\+…\+pmwm)。其中 p i p\_i pi是 n n n的质因子，而 w i w\_i wi则是 p i p\_i pi的次数。

有了这个东西，我们理解欧拉筛法筛约数和就方便多了。

假设现在考虑到 i i i了，那么就按照上面欧拉筛法的两种情况来讨论一下，假设 i i i是素数，那么 s \[ i \] s\[i\] s\[i\]肯定就等于 i + 1 i + 1 i\+1。

假设 i % p r i m \[ j \] ! = 0 i \\% prim\[j\] != 0 i%prim\[j\]!=0，就说明 i i i不包含 p r i m \[ j \] prim\[j\] prim\[j\]这个质因子，但是 s \[ i \] s\[i\] s\[i\]的所有值肯定能对 s \[ i ∗ p r i m \[ j \] \] s\[i \* prim\[j\]\] s\[i∗prim\[j\]\]做上贡献，意思就是说i得质因子肯定是 i ∗ p r i m \[ j \] i \* prim\[j\] i∗prim\[j\]的质因子，所以 s \[ i ∗ p r i m \[ j \] \] s\[i \* prim\[j\]\] s\[i∗prim\[j\]\]中肯定包含了 s \[ i \] s\[i\] s\[i\]，再来看，因为 p r i m \[ j \] prim\[j\] prim\[j\]是素数，他的因子只包含 1 1 1和它本身，因此 i ∗ p r i m \[ j \] i \* prim\[j\] i∗prim\[j\]的因子肯定也只比i多了他的因子乘上 p r i m \[ j \] prim\[j\] prim\[j\]。

不好懂？？这个理解方法确实有点抽象，那么我再来举一个具体的例子：

因为 s ( i ) = ( 1 + p 1 1 + p 1 2 + … + p 1 w 1 ) ( 1 + p 2 1 + p 2 2 + … + p 2 w 2 ) ( 1 + p 3 1 + p 3 2 + … + p 3 w 3 ) … ( 1 + p m 1 + p m 2 + … + p m w m ) s(i) = (1 + p\_1^1 + p\_1^2 + …+ p\_1^\{w\_1\})(1 + p\_2^1 + p\_2^2 + … + p\_2^\{w\_2\})(1 + p\_3^1 + p\_3^2 + … +p\_3^\{w\_3\})…(1 + p\_m^1 + p\_m^2 + … + p\_m^\{w\_m\}) s(i)=(1\+p11\+p12\+…\+p1w1)(1\+p21\+p22\+…\+p2w2)(1\+p31\+p32\+…\+p3w3)…(1\+pm1\+pm2\+…\+pmwm)，且 i i i不包含 p r i m \[ j \] prim\[j\] prim\[j\]这个最小质因子，那么我们假设 p r i m \[ j \] prim\[j\] prim\[j\]为  p m + 1 p\_\{m+1\} pm\+1，它的次数为 1 1 1，  
因此  s ( i ∗ p r i m \[ j \] ) = ( 1 + p 1 1 + p 1 2 + … + p 1 w 1 ) ( 1 + p 2 1 + p 2 2 + … + p 2 w 2 ) ( 1 + p 3 1 + p 3 2 + … + p 3 w 3 ) … … ( 1 + p m 1 + p m 2 + … + p m w m ) ( 1 + p m + 1 1 ) = s ( i ) ∗ ( 1 + p m + 1 ) s(i \* prim\[j\]) = (1 + p\_1^1 + p\_1^2 + …+ p\_1^\{w\_1\})(1 + p\_2^1 + p\_2^2 + … + p\_2^\{w\_2\})(1 + p\_3^1 + p\_3^2 + … +p\_3^\{w\_3\})……(1 + p\_m^1 + p\_m^2 + … + p\_m^\{w\_m\})(1 + p\_\{m + 1\}^1) = s(i) \* (1 + p\_\{m + 1\}) s(i∗prim\[j\])=(1\+p11\+p12\+…\+p1w1)(1\+p21\+p22\+…\+p2w2)(1\+p31\+p32\+…\+p3w3)……(1\+pm1\+pm2\+…\+pmwm)(1\+pm\+11)=s(i)∗(1\+pm\+1)

假设 i % p r i m \[ j \] = = 0 i \\% prim\[j\] == 0 i%prim\[j\]==0，就说明 i = p r i m \[ j \] ∗ x i = prim\[j\] \* x i=prim\[j\]∗x（ x x x同上），而在这里， p r i m \[ j \] prim\[j\] prim\[j\]就相当于 p 1 p\_1 p1，  
因此  s ( i ∗ p r i m \[ j \] ) = ( 1 + p 1 1 + p 1 2 + … + p 1 w 1 + p 1 w 1 + 1 ) ( 1 + p 2 1 + p 2 2 + … + p 2 w 2 ) ( 1 + p 3 1 + p 3 2 + … + p 3 w 3 ) … … ( 1 + p m 1 + p m 2 + … + p m w m ) s(i \* prim\[j\]) = (1 + p\_1^1 + p\_1^2 + …+ p\_1^\{w\_1\} + p\_1^\{w\_1 + 1\})(1 + p\_2^1 + p\_2^2 + … + p\_2^\{w\_2\})(1 + p\_3^1 + p\_3^2 + … +p\_3^\{w\_3\})……(1 + p\_m^1 + p\_m^2 + … + p\_m^\{w\_m\}) s(i∗prim\[j\])=(1\+p11\+p12\+…\+p1w1\+p1w1\+1)(1\+p21\+p22\+…\+p2w2)(1\+p31\+p32\+…\+p3w3)……(1\+pm1\+pm2\+…\+pmwm)。

可是这里一大串等比数列求和太冗杂了，显然一个一个算出来肯定不现实，而我们又想到  
 s ( i ) = ( 1 + p 1 1 + p 1 2 + … + p 1 w 1 ) ( 1 + p 2 1 + p 2 2 + … + p 2 w 2 ) ( 1 + p 3 1 + p 3 2 + … + p 3 w 3 ) … ( 1 + p m 1 + p m 2 + … + p m w m ) s(i) = (1 + p\_1^1 + p\_1^2 + …+ p\_1^\{w\_1\})(1 + p\_2^1 + p\_2^2 + … + p\_2^\{w\_2\})(1 + p\_3^1 + p\_3^2 + … +p\_3^\{w\_3\})…(1 + p\_m^1 + p\_m^2 + … + p\_m^\{w\_m\}) s(i)=(1\+p11\+p12\+…\+p1w1)(1\+p21\+p22\+…\+p2w2)(1\+p31\+p32\+…\+p3w3)…(1\+pm1\+pm2\+…\+pmwm)。

在这里 s ( i ) s(i) s(i)和 s ( i ∗ p r i m \[ j \] ) s(i \* prim\[j\]) s(i∗prim\[j\])相差甚小，我们能用一些什么方法将 s ( i ) s(i) s(i)变成 s ( i ∗ p r i m \[ j \] ) s(i \* prim\[j\]) s(i∗prim\[j\])吗？

答案是肯定的。我们可以记一个数组 p s u m psum psum表示关于 i i i的最小质因子的等比数列求和，那么我们就可以将 s ( i ) s(i) s(i)除掉 p s u m \[ i \] psum\[i\] psum\[i\]，也就是最前面的那一个等比数列，再乘上一个新的等比数列 p s u m \[ i ∗ p r i m \[ j \] \] psum\[i \* prim\[j\]\] psum\[i∗prim\[j\]\]就行了。

当然， p s u m psum psum显然也是可维护的，因为 p s u m \[ i ∗ p r i m \[ j \] \] psum\[i \* prim\[j\]\] psum\[i∗prim\[j\]\]用眼看可发现就等于 p s u m \[ i \] ∗ p r i m \[ j \] + 1 psum\[i\] \* prim\[j\] + 1 psum\[i\]∗prim\[j\]\+1。

至此， s s s的所有情况都已经讨论完毕了。

当然，这道题和欧拉筛法约数和有一个小地方不同，也就是 s \[ i \] s\[i\] s\[i\]不能包括i本身。不过这个应该是个 O I e r OIer OIer都会解决吧、、、

## Code ##

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <cstring>
    #include <iostream>
    using namespace std;
    #define reg register
    #define LL long long
    #define INF 0x3f3f3f3f
    
    template<typename T>
    void re (T &x){ 
        x = 0;
        int f = 1;
        char c = getchar ();
        while (c < '0' || c > '9'){ 
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){ 
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
    
    template<typename T>
    void pr (T x){ 
        if (x < 0){ 
            putchar ('-');
            x = ~x + 1;
        }
        if (x / 10) pr (x / 10);
        putchar (x % 10 + 48);
    }
    
    const int N = 1e7, Maxn = 670000;
    
    int A, B, prim[Maxn + 5], cnt, sum[N + 5], psum[N + 5];
    LL ans;
    bool vis[N + 5];
    
    LL fabs (LL x){ 
        return (x > 0) ? x : ((~x) + 1);
    }
    
    void sieve (int n){ 
    	sum[1] = 1;
        for (int i = 2; i <= n; i++){ 
            if (!vis[i]){ 
                prim[++cnt] = i;
                psum[i] = sum[i] = i + 1;
            }
            for (int j = 1; j <= cnt && i * prim[j] <= n; j++){ 
                vis[i * prim[j]] = 1;
                if (i % prim[j] == 0){ 
                    psum[i * prim[j]] = psum[i] * prim[j] + 1;
                    sum[i * prim[j]] = sum[i] / psum[i] * psum[i * prim[j]];
    				break;
                }
                psum[i * prim[j]] = prim[j] + 1;
                sum[i * prim[j]] = sum[i] * (prim[j] + 1);
            }
        }
    }
    
    int main (){ 
        //freopen ("savrsen.in", "r", stdin);
        //freopen ("savrsen.out", "w", stdout);
        re (A); re (B);
        sieve (B);
        for (int i = A; i <= B; i++){ 
            sum[i] -= i;
            ans = ans + fabs (i * 1ll - sum[i] * 1ll);
        }
        pr (ans);
        putchar (10);
        return 0;
    }

# 后记 #

其实欧拉筛法能筛掉很多东西的，但是因为这道题只和约数和有关，因此我就略掉其他不提，只讲约数和。有兴趣的童鞋可以去康康[这篇同机房ju’lao博客][ju_lao]

[ju_lao]: https://blog.csdn.net/weixin_43896346/article/details/88396182