数学知识算法

来自作者的致歉，由于将来不打算深攻算法，所以本章节内容学的较为肤浅，而且没学完，所以就只写了学了的，内容较少，还望见谅。

试除法

试除法判定质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
bool isprime(int n)
{
    if (n < 2)
        return false;
    if (n == 2)
        return true;
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int x;
        scanf("%d", &x);
        if (isprime(x))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}

这个就是一个普通的判定质数的优化，关于每次判断条件时对于除数的判断，不需要枚举到n，因为我们发现，一个数的约数，都是成对存在的（包括1和他本身），这也就说明，如果他能被小的那个数整除也就能被大的那个数整除，所以我们在枚举的时候就只需要枚举到平方除，此时两个根相等，而后面的数都有一个对应的约数与前面等价，所以就只用枚举到sqrt，这样能节省时间。从O（n）变成O（sqrt（n））。

试除法求约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> getdivisors(int n)
{
    vector<int> res;
    for (int i = 1; i <= n/i;i++)
    {
        if(n%i==0)
        {
            res.push_back(i);
            if(i!=n/i)
            {
                res.push_back(n / i);
            }
        }

    }
    sort(res.begin(), res.end());
    return res;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x;
        cin >> x;
        auto res = getdivisors(x);
        for(auto t:res)
        {
            cout << t << ' ';
        }
        cout << endl;
    }
    return 0;
}

与试除法求质数相似，也是从1开始，不断遍历到sqrt（n），取出能整除的i放入vector数组，有一点需要注意的就是，如果i能被放入数组的话，那么n/i也可以，所以这里就把两个数都放进数组，但是，需要注意的就是，如果i是sqrt(n)的话，那么i=n/i，此时就只放入一个数就可以了。

试除法分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 110;
int n;
void divide(int n)
{
    for (int i = 2; i <= n / i; i++)
    {
        if (n % i == 0)
        {
            int s = 0;
            while (n % i == 0)
            {
                n /= i;
                s++;
            }
            printf("%d %d\n", i, s);
        }
    }
    if (n > 1)
        printf("%d %d\n", n,1);
    puts("");
}
int main()
{
    scanf("%d", &n);
    while (n--)
    {
        int x;
        scanf("%d", &x);
        divide(x);
    }
    return 0;
}

注意在搜寻质因数的时候，我们选择枚举所有数，这里有个很巧妙的点，就是说，如果我们枚举到i了，那么说明我们已经枚举完了前面i-1个数，说明此时n已经不能被前面i-1中任意一个数整除，那么此时如果找到一个合数，他根本不可能整除此时的n，因为n在已经被他的质因数除过了。所以这里就能大幅缩减我们判断质因数的难度与时间复杂度。、
又因为，质因数也可能是他本身，这样就大于sqrt（n）了，但是这样的数只存在一个，因为如果存在两个以上，那么i×i大于n了，不成立，所以就只用判断最后一次遍历玩前sqrrt个数之后，此时的n是否大于1，如果大于1就再把这个n加进来。
本题难点：
1、遍历时枚举所有数，合数自然会被排除掉。
2、优化枚举的数到sqrt，最后一个数直接输出枚举后大于1的情况就行了。

筛法

筛质数

c++基本筛质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void getprime(int n)
{
    for (int i = 2; i <= n;i++)
    {
        if(!st[i])
            primes[cnt++] = i;
        for (int j = i + i; j <= n;j+=i)
        {
            st[j] = true;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    getprime(n);
    printf("%d", cnt);
    return 0;
}

普通的筛质数就是先判断这个数是否标记，如果没有被标记的话，那就加入这个数，这个数就是质数，然后再把这个数的所有倍数都标记了，依次类推，就能把所有合数标记，质数不被标记。

埃式筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void getprime(int n)
{
    for (int i = 2; i <= n;i++)
    {
        if(!st[i])
	    {
	        primes[cnt++] = i;
	        for (int j = i + i; j <= n;j+=i)
	        {
	            st[j] = true;
	        }
        }
    }
}
int main()
{
    int n;
    cin >> n;
    getprime(n);
    printf("%d", cnt);
    return 0;
}

在基础筛法的基础上，我们进行优化，我们会发现，如果一个数是质数的话，那么她一定存在质因数，而这个质因数的倍数一定包含这个数和她的倍数，所以此时如果我们再去遍历这个合数的倍数的话，我们就会重复遍历，这样很浪费时间，所以我们就做一点小小的优化，对所有的质数进行上述操作，即为在判断完这是质数之后就直接进行遍历操作。

线性筛法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void getprime(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
            primes[cnt++] = i;
        for (int j = 0; primes[j] <= n;j++)
        {
            st[primes[j] * i] = true;
            if(i%primes[j] == 0)
                break;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    getprime(n);
    printf("%d", cnt);
    return 0;
}

线性筛法之所以叫线性筛法，是因为每一个数都只筛选了一遍，通过埃式筛法我们已经初步对算法进行了优化，但是我们发现即使是质数也会存在重复筛选，因此我们想：能不能存在一种筛法，让所有的数只被筛选一次，这样就能最大化节省时间。
哈哈，我们想到如果一个质数乘以另一个质数的话，那么这个数的最小质因数一定是这两个数中的一个，聪明的我们想到，一个数最多只存在一个最小质因数，那也就是说一个i×一i个比他小的质数一定会得到一个最小质因数是那个质数的数，因此我们就能找到一个唯一值，当这个质数大于i时，最小质因数就不一定时i了，就可能存在重复，因此问题就一目了然了。
我们遍历每一个质数，如果他不是i的最小质因数，就让他×i然后标记这个数，并继续遍历，如果这个数恰好是最小质因数，就离开循环，因为再往后就可能存在i的最小质因数不是j但是仍然遍历了之前遍历过的一个数字，就重复搜索了。
这样的话我们就只有一次遍历，完全线性。

欧拉公式-求互质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a;
        cin >> a;
        int res = a;
        for (int i = 2; i <= a / i;i ++)
        {
            if(a % i == 0)
            {
                res = res / i * (i - 1);
                while(a % i == 0)
                {
                    a /= i;
                }
            }
        }
        if(a > 1)
            res = res / a * (a - 1);
        cout << res << endl;
    }
    return 0;
}

互质数就是两个数之间没有除了1以外的数能相互整除。
此时我们一定能想到的就是，用N减去所有N的质因数和他对应的倍数，但是这里我们就会发现一个问题，如果直接这样的话，我们就会发现有些数反复被减去了，那么我们就要对这些数进行一些处理。我们会发现单数个数乘积组成的数应该减去，双数个数组成的数乘积应该加上。

在此基础之上，我们再利用容斥原理，就能得到一个公式：
N = N (1 - 1 / p1) (1- 1 / p2) …… (1 - 1 / pk)

本题难点：
1、关于是否能想到这个公式。
2、对于公式的实现，在实现过程中，因为我们的数都是整数运算，所以我们要做一点变式：
res = res / i * (i - 1)

筛法求欧拉函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1000010;
int primes[N], cnt;
int phi[N];
bool st[N];
ll get_eulers(int n)
{
    
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            phi[i] = i - 1;
        }
            
        for (int j = 0; primes[j] <= n / i;j++)
        {
            st[primes[j] * i] = true;
            if(i%primes[j] == 0)
            {
                phi[primes[j] * i] = primes[j] * phi[i];
                break;
                
            }
            phi[primes[j] * i] = (primes[j] - 1) * phi[i];
        }
    }
    ll res = 0;
    for (int i = 1; i <= n; i ++)
    {
        res += phi[i];
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    cout << get_eulers(n) << endl;
    return 0;
}

在筛法的基础之上，我们在进行求欧拉，对于从1到N的每一个数的互质数的个数，我们使用筛法，先线性求出质数，再在质数的基础之上，如果一个数是质数的话，那么这个数的互质数的个数就是i-1。如果这个数是满足i / primes[j] == 0 && x = i * primes[j]，那么我们能发现根据欧拉公式，这个数与i之间的所有质因数是完全一样的，那么这个数的互质数的个数就与i的互质数的个数，只相差一个primes[j]。如果不能整除的话，我们就能发现跟i的互质数相比，该数多了一个primes[j]，那么就乘上一个（1 - 1 / primes[j]）再 × primes[j]。最后在根据线性筛法，这样的算法每一个数都能被求一遍，所以也就找到了每一个数的互质数。

本题难点：
1、关于筛法的使用和理解。（为何要使用筛法）：线性的算法，能有效减少是时间复杂度，而且能够找出所有质数，与唯一以他为最小质因数的所有数。
2、关于欧拉公式的活运用。也就体现在那一步找规律那里。
3、小心所有的数加起来爆int，注意合理使用long long。

约数

最大公约数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
int gcd(int a,int b)
{
    return b ? gcd(b, a % b) : a;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a, b;
        cin >> a >> b;
        printf("%d\n", gcd(a, b));
    }
    return 0;
}

关于最大公约数有一个原理，就是如果d同时能整除a和b那么d就能同时整除a和a%b。
在这一点的基础之上我们就能对每一次的a和b进行取模操作，达到找出最大公约数的效果，如果b不为0，那么就递归求b，a % b的函数，直到a % b = 0。说明此时a已经能与b相整除了，此时一定有a一定满足整除两边数，所以为最大公约数。
省流：背板子。

约数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
int main()
{
    int n;
    cin >> n;
    unordered_map<int, int> primes;
    while(n--)
    {
        int x;
        cin >> x;
        for (int i = 2; i <= x / i; i++)
        {
            while (x % i == 0)
            {
                x /= i;
                primes[i]++;

            }
        }
        if(x>1)
            primes[x]++;
    }
    ll res = 1;
    for(auto prime : primes)
    {
        res = res * (prime.second + 1) % mod;
    }
    cout << res << endl;
}

约数个数的基础是找到约数，找约数的过程也是前面讲到的试除法找约数。
这道题的重点是找到约数的所有个数的求法：

关于约数之和，其实就是把每一个具体的约数加起来，对于每一个p，不管是p的几次方，都对应一个具体的约数，因此，每一个p的不同次方都会被加进这个数。所以，我们就对于每一个p的不同次方进行求和，也就得到了：
思路大致就是这样
那么这道题的代码实现也就不难发现：因为我们要找这几个数的乘积的约数个数，其实也就只需要找到每一个数的约数对应的指数，然后再使用公式直接×起来就ok了。我们会发现我们需要分别用到一个数和与他绑定的对应的指数，所以我们就使用#include这里我们定义一个哈希表，用它来进行我们对应约数的指数运算。注意，到了最后如果x还大于1，说明这时x本身是一个质数，所以我们就还要把x也加入进去。
本题难点：
1、哈希表的建立与正确使用
2、该算法中的数学思想的发现与正确实现
3、因为数据会很大，所以开long long。
4、代码最后使用 % mod 的原因是为了防止整数溢出。