质数 质因数 约数 公约数 快速幂

质数 质因数 约数 公约数 快速幂

1、质数的判定————试除法

时间复杂度：

​ O(sqrt(n))

核心思路：

​ 优化： | 表示整除，如果d | n，显然n / d | n 一定成立，因为d的约数一定是成对出现的，而这一对就是d 和 n / d，
故我们在枚举的时候，只需要枚举较小的那个就能判定当前这对是不是该数的约数，如下：
​ d <= n / d， d ^ 2 <= n， d <= 根号n，就把上面的O(n)的复杂度降到了O(根号n)。

代码模板：

bool is_prime(int n)
{
    if (n < 2) return false;
    for (int i = 2; i <= n / i; i ++)
        if (n % i == 0) 
            return false;
    return true;
}

注意：

在判断的时候，一定要记得特判小于2的所有数，都不是质数。

2、分解质因数：

时间复杂度：

​ O（sqrt(N)）

核心思路：

​ 从小到大枚举所有数，即从小到大尝试n的所有质因数，并求其次数。

代码模板：

for (int i = 2; i <= n; 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);

注意：

​ （1）、关于枚举时，为什么一定不会枚举到合数？
​ 答： 当我们枚举到i时，就说明n当中，已经不包含任何2 ~ i - 1的质因子了，
​ 然后n能整除i，说明i当中也不包含任何2 ~ i - 1的质因子了，因此i一定是一个质数
​ （2）、n中最多只包含一个大于sqrt(n)的质因子，故在枚举时，可以先把所有小于sqrt(n)的质因子枚举出来，
​ 最后将大于sqrt(n)的质因子特判输出即可。————————这样时间复杂度就从O(n)降到了O(sqrt(n));

3、线性筛法： 筛质数

时间复杂度：

​ O(n)

核心思路:

​ 核心：每一个数i，只会被其最小质因子筛掉。
​ 分析：在筛掉时候，是从小到大枚举所有质数，每次把当前质数和i的乘积筛掉，当 i % primes[j] == 0成立时，
​ 说明primes[j] 一定是i的最小质因子，因为primes[j]是从小到大枚举的，且所有的质数都放在了primes里。

代码模板：

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] <= n / i; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

注意点：

​ 1、因为prime中素数是递增的，所以如果i%prime[j]!=0代表i的最小质因数还没有找到，
​ 即i的最小质因数大于prime[j]。也就是说prime[j]就是iprime[j]的最小质因数，于是iprime[j]被它的最小质因数筛掉了。

​ 2、如果当i%prime[j]==0时，代表i的最小质因数是prime[j]，
​ 那么iprimej+k这个合数的最小质因数就不是prime[j+k]而是prime[j]了。
​ 所以iprime[j+k]应该被prime[j]筛掉，而不是后续的prime[j+k]。于是在此时break。

​ 3、对于一个合数x，假设primes[j]是x的最小质因子，当i枚举到x / primes[j]时，i就会被筛掉，且一定是被其最小质因子筛掉的。

4、试除法求约数

时间复杂度：

​ O(sqrt(n))

核心思路：

​ 试除法求约数：
（1）i从1开始，遍历到n / int
（2）每找到一个约数：
​ （2.1）就将它约数放入数组中，
​ （2.2）判断一个n / i == i，如果不相等，就把他放入数组中
（3）找完之后sort一下，即可获得从小到大的一个数的约数数组
​ 优化同质数，一个数的约数也是成对出现的，故在枚举时，直接枚举较小的约数即可，即i <= sqrt(n)

代码模板：

 vector<int> get_divisors(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;
}

5、约数个数：

核心思路：

​ N = p1 ^ a1 * p2 ^ a2 * … * pk ^ ak
​ 则约数个数为cnt = (a1 + 1)(a2 + 2)…(ak + 1)，证明：
​ N = p1 ^ a1 * p2 ^ a2 * … * pk ^ ak
​ 因为N的任意一个约数d，都可以写作d = p1 ^ b1 * p2 ^ b2 * … * pk ^ bk, 0 <= bi <= ai，
​ pi每一项的指数b如果不同，则构成的约数就不同，故对于每一个pi都有(ai + 1)种情况，故约数个数就有(ai + 1)个。
​ 而对于N来说，N的每一个约数，都对应了b1 ~ bk的不同取法，则选法种数即为约数个数，
​ 故约数个数则为cnt = (a1 + 1)(a2 + 1)…(ak + 1)

​ int范围内，约数个数最多的数只有1500~1600个。

代码模板：

#include <iostream>
#include <unordered_map>

using namespace std;

const int  mod = 1e9 + 7;

long long res;

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] ++;
    }
    res = 1;
    for (auto prime : primes) res = res * (prime.second + 1 ) % mod;

    cout << res << endl;

    return 0;
}

注意：

​ 约数个数 = 分解质因数后，（所有指数 + 1）相乘

6、约数之和

核心思路：

​ N = p1 ^ a1 * p2 ^ a2 * … * pk ^ ak
​ 则约数之和为sum = (p1 ^ 0 + p1 ^ 1 + … + p1 ^ a1) * … *(pk ^ 0 + pk ^ 1 + … + pk ^ ak)，证明：
​ 用乘法分配律将上式展开，就是一堆乘积（） + 一堆乘积（） + （）…
​ 而（）则是从上式括号中每一个括号中任取一项组成的，任意一堆乘积（）都是一个约数，
​ 故这个公式就是将所有约数加在一起了。

代码模板：

#include <iostream>
#include <unordered_map>

using namespace std;

long long res;

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] ++;
    }

    res = 1;
    for (auto prime : primes)
    {
        long long a = prime.first, b = prime.second;
        long long t = 1;
        while (b --) t = (t * a + 1) % mod;
        res = res * t % mod;

    }
    cout << res;


    return 0;
}

注意：

​ 约数之和 = 因式分解后（所有幂的0~其指数次方之和）的乘积

7、最大公约数：

核心思路:

​ d | a, d | b，则d | (a + b) = d | ax + by，
​ (a, b)的最大公约数 = (b, a % b) 的最大公约数。

​ 证明：a mod b = a - (a/b) * b = a - c * b
​ (a, b) = (b, a - c * b)，d | a, d | b，所以d | (a - c * b)成立
​ d | b, d | a - c * b,则d | a - c * b + c * b，即d | a，所以右边的公约数 = 左边的公约数，左边的公约数等于右边的公约数
​ 故，(a, b) = (b, a mod b)成立

代码模板：

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

8、快速幂：

核心思路：

反复平方法。
预处理出来一些值：a ^ (2 ^ 0) mod p, a ^ (2 ^ 1) mod p,,,a ^ (2 ^ logk) modp的值,共logk个，
用这些值去组合出a ^ k
a ^ k = a ^ (2 ^ x1) * a ^ (2 ^ x2) … * a ^ (2 ^ xt)
= a ^ (2 ^ x1 + 2 ^ x2 + …2 ^ xt)，即把k拆分成2^x1,2^x2,,,2^xt这logk个数的和。
（1）拆k的方式：把k用二进制表示，把二进制数下是1的位，加上其所属幂位即可，
例k的二进制表示为： 110110，k = 2^1 + w^2 + 2^4 + 2^5，
（2）如何预处理出我们所需要的值：
第一个数a^(2^0) = a^1 = a,后面每个数都是前面一个数的平方。

代码模板：

//返回的就是a^k % p
int qmi(int a, int k, int p)
{
    int res = 1;
    while (k)
    {
        if (k & 1) res = (LL) res * a % p;  //当前位是1，则前位更新到答案中
        k >>= 1;    //算过的位删掉
        a = (LL) a * a % p;//把a变成下一个
    }

    return res;
}

注意：

​ 一定一定要注意每个运算的地方都要进行(long long)的转换，以及 取模%p