试除法判定质数

1
2
3
4
5
6
7
8
9
10
11
12
int n;
int a;
bool pr(int a)
{
    if(a < 2) return false;
    // 写sqrt()函数调用太多拖慢时间，写i*i<a可能会溢出  当a是2时，2 <= 1因此不会进入循环
    for(int i = 2; i <= a/i; i ++)   
    {
        if(a % i == 0) return false;
    }
    return true;
}

分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n;
void divide(int n)
{
    // 由于一个数有且只有一个大于sqrt(n)的质因子，故i枚举到sqrt(n)即可，大于根号n的质因子进行特判。
    for(int i = 2; i <= n/i; i ++)  
        if(n % i == 0)   // 满足这个条件的话，i一定为质数，合数会被i的倍数筛除
        {
            int s =0;
            while(n % i == 0)
            {
                n /= i;
                s ++;
            }
            cout << i << " " << s << endl;
        }
    if(n > 1) printf("%d %d\n",n,1);
    cout << endl;

}

埃氏筛法

筛法例子展示
思路：
从小到大利用质数将质数的合数筛除(进行标记)
时间复杂度$O(nlog(logn))$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int N =1000010;

int st[N],primes[N];  // st[N]用来标记是质数还是合数。primes[N]为质数表
int n,cnt;

void get_primes(int n)
{
    for(int i = 2; i <= n; i ++)
    {
        if(!st[i])      // 如果是质数进行下列操作
        {
            primes[cnt ++] = i;    // 放入质数表中
            for(int j = i; j <=n; j += i) st[j] = 1;  // 将质数的倍数标记为合数
        }
    }
}

线性筛法

埃氏筛法中一个合数会被不同的质因子筛多次，线性筛保证每个数只被其最小质因数筛去，如何实现呢？令循环在i %primes[j] == 0时退出
步骤：之前每筛到一个素数，便将这个素数放入到primes[ ]中，在每次循环中，从头开始遍历primes[ ]， 筛选出的合数为 primes[j]×i
那么如何保证每个数都只被筛选一次？即循环应该在何时结束？
筛质数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int n;
void divide(int n)
{
    // 由于一个数有且只有一个大于sqrt(n)的质因子，故i枚举到sqrt(n)即可，大于根号n的质因子进行特判。
    for(int i = 2; i <= n/i; i ++)  
        if(n % i == 0)   // 满足这个条件的话，i一定为质数，合数会被i的倍数筛除
        {
            int s =0;
            while(n % i == 0)
            {
                n /= i;
                s ++;
            }
            cout << i << " " << s << endl;
        }
    if(n > 1) printf("%d %d\n",n,1);
    cout << endl;

}

试除法求约数

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
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;
}
int main()
{
    int n;
    cin >> n;
    while(n -- )
    {
        int a;
        cin >> a;
        vector<int> res = get_divisors(a);
        for(auto t : res)
        {
            cout << t << " ";
            
        }
        cout <<endl;
    }
    return 0;
}

约数个数

约数个数定理：
若 $n=\prod_{i=1}^{s} p_{i}{ }^{\alpha_{i}}$ , 则 $d(n)=\prod_{i=1}^{s}\left(\alpha_{i}+1\right)$ 。
一个数的约数是由其质因数分解中质因数的所有取法排列组合出来的
证明:
$p_{i}{ }^{\alpha_{i}}$ 的约数有 $p_{i}^{0}, p_{i}^{1}, \cdots, p_{i}^{\alpha_{i}}$ 共 $\left(\alpha_{i}+1\right)$ 个,
根据乘法原理, $d(n)=\prod_{i=1}^{s}\left(\alpha_{i}+1\right)$ 。
unordered_map中存储质因子及其指数

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<unordered_map>
using namespace std;

const int mod = 1e9 + 7;
typedef long long LL;
int main()
{
    int n;
    cin >> n;
    unordered_map<int,int> primes;
    while(n --)
    {
        int a;
        cin >> a;
        for(int i = 2; i <= a/i; i ++)
        {
            while(a % i == 0)
            {
                a /= i;
                primes[i] ++;    // primes[]中存储i的指数
            }
        }
        if(a > 1) primes[a] ++ ;
    }
    LL res = 1;
    for(auto p : primes) res = res * (p.second + 1)% mod;
    cout << res <<endl;
    return 0;
}

约数之和

若 $n=\prod_{i=1}^{s} p_{i}{ }^{\alpha_{i}}$ , 则 $d(n)=\prod_{i=1}^{s}\left(\alpha_{i}+1\right)$ 。
约数本就是由其质因数分解中质因数的所有取法(即约数)排列组合出来的
故其和便是 这些排列组合的相加
证明:
$p_{i}{ }^{\alpha_{i}}$ 的约数有 $p_{i}^{0}, p_{i}^{1}, \cdots, p_{i}^{\alpha_{i}}$ 共 $ \left(\alpha_{i}+1\right)$ 个,
其约数和为：$\sum_{j =0} ^{\alpha i}p_i$
根据乘法原理, $f(n)=\prod{i=1}^{s}\sum_{j =0} ^{\alpha _i}p_i^j$

其各个质因数的幂次的约数和(t = (t * a + 1) )的乘积(展开之后) 等于 一个数的约数和
$f(n)= (p_1 ^0 +p_1^1 +p_1^2 \cdots+p_1^{\alpha_1})\times (p_2 ^0 +p_2^1 +p_2^2 \cdots+p_2^{\alpha_2})\times \cdots (p_i ^0 +p_i^1 +p_i^2 \cdots+p_i^{\alpha_i})$
例：
$12 = 2^2 \times 3 ^ 1$
$f(n)=(1 + 2 + 4) \times ( 1 +3) = 7 \times 4 = 28$

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
#include<iostream>
#include<unordered_map>
using namespace std;
const int mod = 1e9 +7;
typedef long long LL;
int main()
{
    int n; cin >> n;
    unordered_map<int, int> prime;
    while(n --)
    {
        int x;
        cin >> x;
        for(int i =2; i <= x/i; i ++)
        {
            while(x % i ==0) 
            {
                prime[i] ++;
                x /= i;
            }
        }
        if(x > 1) prime[x]++;
    }
    LL res = 1;
    for(auto p: prime)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while(b --) t = (t * a + 1) %mod;
        res =res * t %mod;
    }
    cout << res <<endl;
    return 0;
}

最大公约数

1
2
3
4
5
int gcd(int a, int b)
{
    return b ? gcd(b, a%b) : a;
}