首页 algorithm 算法OJ Acwing

# 筛质数

利用最小质因子进行判断

if(i % prime[j] == 0) break;

  1. 如果 i % primes[j]!=0 ，说明 primes[j] 不是 i 的质因子，那么只可能是此时的 primes[j]*i 的最小质因子，所以 primes[j] * i 的最小质因子就是 primes[j]
  2. 如果 i % primes[j]==0 ，说明 i 的最小质因子是 primes[j] , 因此 primes[j]*i 的最小质因子也就应该是 prime[j] ，之后接着用 st[primes[j+1]*i]=true 去筛合数时，就不是用最小质因子去更新了，因为 i 具有更小的质因子 prime[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
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
bool st[N];
int prime[N], cnt;
int n;
int get_prime()
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; j++)//把小于n的数进行判断
        {
            st[prime[j] * i] = true;//用最小质因子筛质数
            if(i % prime[j] == 0) break;
        }   
    }
    return cnt;
}
int main()
{
    cin >> n;
    cout << get_prime();
    return 0;
}

# 二次筛质数

  1. 因为数据最大是2312^{31}，所以显然不能用线性筛，会 TLE
  2. 用二次筛：假设一个数 n 是合数，那么它一定有d,ndd,\frac{n}{d} 两个因子，假设d<ndd<\frac{n}{d}，则d<nd<\sqrt{n}，所以只需要找出1∼n1\sim\sqrt{n} 的所有素数，然后用这些素数更新[l,r][l,r] 的所有合数即可
  3. 对于素数 p，要找到[l,r][l,r] 中所有以 p 为最小质因子的合数，可以从 max(2 * p, (l + p - 1) / p * p) 开始寻找，然后不断 +p 即可，其中 (l + p - 1) / p * p 等价于⌈lp⌉\lceil\frac{l}{p}\rceil
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
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
int prime[N], cnt;
ll prime2[N], k;
bool st[N];

void get_prime(int n)
{
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}
int main()
{
    int l, r;
    get_prime(50000);
    while(scanf("%d%d", &l, &r) != -1)
    {
        memset(st, 0, sizeof st);
        memset(prime2, 0, sizeof prime2);
        k = 0;
        for(ll i = 0; i < cnt; i++)
        {
            ll p = prime[i];
            for(ll j = max(2 * p, (l + p - 1) / p * p); j <= r; j += p)
                st[j - l] = true;   
        }
        for(int i = 0; i <= r - l; i++)
        {
            if(!st[i] && i + l > 1)
                prime2[k++] = i + l;
        }
        if(k < 2) cout << "There are no adjacent primes." << '\n';
        else
        {
            int minp = 0, maxp = 0;
            for(int i = 0; i + 1 < k; i++)
            {
                int d = prime2[i + 1] - prime2[i];
                if(d < prime2[minp + 1] - prime2[minp]) minp = i;
                else if(d > prime2[maxp + 1] - prime2[maxp]) maxp = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", prime2[minp], prime2[minp + 1], prime2[maxp], prime2[maxp + 1]);
        }
    }
    return 0;
}

# 阶乘分解

对于 8！

1 2 3 4 5 6 7 8

平时的方法是每个数每个数地求，即每一列每一列地求，但是这样的效率太低，于是想到一行一行地求

  • 求出 8！中 2 的倍数

1 2 3 4 5 6 7 8

​ 1 1 1 1 首先我们1∼81\sim 8 中 2 的个数： 8 / 2

​ 1 1 然后求出1∼81\sim 8 中 4 的个数： 8 / 4

​ 1 最后求出1∼81\sim 8 中 8 的个数： 8 / 8

所以 8！中因数 2 的个数： 8 / 2 + 8 / 4 + 8 / 8 = 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;
int prime(int x)
{
    if(x == 2) return 1;
    for(int i = 2; i <= x / i; i++)
    {
        if(x % i == 0) return 0;
    }
    return 1;
}
int main()
{
    int n;
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        if(!prime(i)) continue;
        long long x = i, ans = 0;//因为n！可能很大，所以用long long存储x
        while(x <= n) ans += n / x, x *= i;
        cout << i << " " << ans << '\n';
    }
    return 0;
}

# 约数个数

把一个数 N 写成N=p1x1⋅p2x2⋅...⋅pkxkN=p_1 ^ {x_1}\cdot p_2^{x_2}\cdot ... \cdot p_k^{x_k}, 则约数个数为(x1+1)(x2+1)...(xk+1)(x_1+1)(x_2+1)...(x_k+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
#include <iostream>
#include <unordered_map>
using namespace std;
const int mod = 1e9 + 7;
unordered_map<int, int> mp;
typedef long long ll;
int main()
{
    int n; cin >> n;
    ll res = 1;
    while(n--)
    {
        int a;  cin >> a;
        for(int i = 2; i <= a / i; i++)
        {
            while(a % i == 0)
            {
                a /= i;
                mp[i]++;
            }
        }
        if(a > 1) mp[a]++;
    }
    for(auto& [x, y] : mp)
    {
        res = res * (y + 1) % mod;
    }
    cout << res;
    return 0;
}

# 约数之和

把一个数 N 写成N=p1x1⋅p2x2⋅...⋅pkxkN=p_1 ^ {x_1}\cdot p_2^{x_2}\cdot ... \cdot p_k^{x_k}, 则约数之和为(p10+p11+...+p1x1)×...×(pk0+pk1+...+pkxk)( p_1^0+p_1^1+..._+p_1^{x_1})\times...\times (p_k^0+p_k^1+...+p_k^{x_k})

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

# 最大公约数

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

# 欧拉函数

1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。若在算数基本定理中，N=p1a1p2a2…pmamN=p_1^{a_1}p_2^{a_2}…p_m^{a_m}，则：
ϕ(N) = N×\frac{p_1 - 1}{p_1}×\frac{p_2−1}{p_2}×…×\frac{p_m−1}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;
typedef long long ll;
int main()
{
    int n;  cin >> n;
    while(n--)
    {
        int a;  cin >> a;
        ll 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 << '\n';
    }
    return 0;
}

# 筛法求欧拉函数

给定一个正整数 n，求 1∼n 中每个数的欧拉函数之和。欧拉函数是指1∼N1\sim N 中与 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
40

1. ```i % prime[j] == 0```，在此情况下```prime[j]```是```i```的质因子，所以```i```和```i * prime[j]```的质因子是相同的，所以根据公式，```ph[i * prime[j]] = ph[i] * prime[j]```，即只差N中的```prime[j]```
2. ```i % prime[j] != 0```，在此情况下```prime[j]```不是```i```的质因子，所以```i```和```i * prime[j]```的质因子相差一个```prime[j]```，所以根据公式，```ph[i * prime[j]] = ph[i] * prime[j] * (1 - 1 / prime[j]) = ph[i] * (prime[j] - 1)```，即差N中的```prime[j]```和质因子的一项```1 - 1 / prime[j]```

```c++
#include <iostream>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
ll phi[N], prime[N];
bool st[N];
ll n, cnt;

int main()
{
   cin >> n;
   phi[1] = 1;
   for(int i = 2; i <= n; i++)
   {
       if(!st[i])
       {
           phi[i] = i - 1;
           prime[cnt++] = i;
       }
       for(int j = 0; prime[j] <= n / i; j++)
       {
           st[prime[j] * i] = true;
           if(i % prime[j] == 0) 
           {
               phi[i * prime[j]] = phi[i] * prime[j];
               break;
           }
           else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
       }
   }
   ll res = 0;
   for(int i = 1; i <= n; i++) res += phi[i];
   cout << res;
   return 0;
}

# 快速幂

给定 n 组ai,bi,pia_i,b_i,p_i，对于某组数据，求出aibimodpia_i^{b_i}modp_i

  1. 如果直接暴力枚举，时间复杂度是O(b∗n)O(b*n)，会 TLE
  2. 将 b 用二进制表示，b=2x1+2x2+...2xnb = 2^{x_1}+2^{x_2}+...2^{x_n}；预处理出a20,a21,...a2logba^{2^0},a^{2^1},...a^{2^{logb}}
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
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n;
typedef long long ll;
ll qmi(ll a, ll b, ll p)
{
    ll ans = 1;
    while(b)
    {
        if(b & 1) ans = ans * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return ans;
}
int main()
{
    cin >> n;
    while(n--)
    {
        ll a, b, p;
        cin >> a >> b >> p;
        cout << qmi(a, b, p) % p << '\n';
    }
    return 0;
}

# 快速幂求逆元

直接根据公式bm−2b^{m-2} 即为 b 的乘法逆元，求解即可

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
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
typedef long long ll;
ll qmi(ll a, ll b, ll p)
{
    ll res = 1;
    while(b)
    {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        ll a, p;
        cin >> a >> p;
        ll res = qmi(a, p - 2, p);
        if(a % p == 0) cout << "impossible" << '\n';
        else cout << res << '\n';
    }
    return 0;
}