算法-蓝桥杯真题（2）

最大公约数（GCD）

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

试除法分解质因数

1
2
3
4
5
6
7
8
9
10
11
12
void divide(int x)
{
    for(int i = 2;i <= x / i;i ++)
    {
        if(x % i == 0) // i 一定是质数
        {
            int s = 0; // 记录同一个质数出现的次数
            while(x % i == 0) x /= i, s ++;
        }
	}
    if(x > 1) cout << x << " " << 1 << endl; // 当x最后还大于1说明剩下的是大于sqrt(x)的质因数
}

例题

image-20250402200013334

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

int a, b;

// 试除法分解质因数
void divide(int x)
{
	int t = x;
	//unordered_map<int, int> mp;
	vector<int> ans;
	for(int i = 2;i <= x / i;i ++)
	{
		if(x % i == 0) // i 一定是质数
		{
			int s = 0;
			while(x % i == 0)
			{
				ans.push_back(i);
				x /= i;
			}
		}
	}
	if(x > 1)
	{
		ans.push_back(x);
	}

	printf("%d=", t);
	for(int i = 0;i < ans.size();i ++)
	{
		if(i == ans.size() - 1)
			printf("%d\n", ans[i]);
		else
			printf("%d*", ans[i]);
	}	
}

int main()
{
	cin >> a >> b;
	for(int i = a;i <= b;i ++)
	{
		divide(i);
	}
    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
29
// 埃氏筛
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n)
 {
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i + i; j <= n; j += i)
            st[j] = true;
    }
 }

// 线性筛
int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
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;
        }
    }
 }

image-20250402211152112

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
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 25;

bool is_prime[N * 2];
vector<int> ans(N);
bool vis[N];
bool flag = false;
int n;

void init(int n)
{
	fill(is_prime, is_prime + N, true);
	is_prime[0] = is_prime[1] = false;
	for(int i = 2;i <= n;i ++)
	{
		if (is_prime[i])
			for(int j = i + i;j <= n;j += i)
		 		is_prime[j] = false;
	}
}
 
void dfs(int dep)
{
	if(dep == n)
	{
		// 检查首尾和是否为素数
        if(is_prime[ans[0] + ans[n-1]]) 
        {
	        for(int i = 0; i < n; i++)
	        {
	            cout << ans[i] << " \n"[i == n-1];
	        }
	        flag = true;
        }
        return;
	}
	
	for(int i = 2;i <= n;i ++)
	{
		if(!vis[i] && (dep == 0 || is_prime[i + ans[dep-1]]))
        {
            vis[i] = true;
            ans[dep] = i;
            dfs(dep + 1);
            vis[i] = false;
        }
	}
}

int main()
{
	cin >> n;
	if(n == 1)
	{
		cout << 1 << endl;
		return 0;
	}
	init(n * 2);
	ans[0] = 1;
	dfs(1);
	if(flag == false) cout << "No Answer";
    return 0;
}

image-20250402211250751

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

bool st[N];
int primes[N];
int cnt;

int main()
{
	int n; cin >> n;
	for(int i = 2;i <= n;i ++)
	{
		if(st[i]) continue;
    primes[cnt ++] = i;
    for(int j = i + i; j <= n;j += i)
      st[j] = true;
	}
	cout << cnt << endl;
	return 0;
}

// 如果需要质数表，我们优先选择线性筛，这里我们默写一遍试一下
int primes[N], cnt;
bool st[N]; // 标记是否是合数，也就是是否被筛掉，被筛掉就是质数
void get_primes(int n)
{
    for(int i = 2;i <= n;i ++)
    {
        if(!st[i]) primes[cnt ++] = i; // 如果i不是合数就加入到质数中
        for(int j = 0; primes[j] <= n / i;j ++)
        {
            // 这里是用已经有的质数来筛后边的数字
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break; // 这是优化的关键，这里保证我们只用每个数字的最小质因数筛掉它，保证了线性的时间复杂度
		}
	}
}

快速幂

  • 快速幂 的本质就是将我们的指数进行 二进制的分解 来提高我们计算的速度
  • 详情见：快速幂 - OIWiki

image-20250402214036610

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 10;

long long b, p, k;

int main()
{
	cin >> b >> p >> k;
	long long res = 1;
	while(p)
	{
		if(p & 1) res = res * b % k;
		b = b * b % k;
		p >>= 1;
	}
	cout << res << endl;
	return 0;
}

乘法逆元

  • 乘法逆元原理在这里不做讲解，只要记住逆元就是运用快速幂函数即可实现为 qmi(a, p - 2) $p$ 是一个质数

image-20250402214626702

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 <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;

const int N = 1e5 + 10;
const int mod = 1e9 + 7;

ll qmi(ll a, ll b)
{
	ll res = 1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void solve()
{
	ll n; cin >> n;
	cout << qmi(n, mod - 2) << endl;
}

int main()
{
	int t; cin >> t;
	while(t --) solve();
	return 0;
}

image-20250402221710994

  • 这个题的查询次数较多且 n 和 m 较大
  • 我们使用了预处理的方式来优化，其中我们要预处理逆元阶乘数组和阶乘数组，比较复杂，需要有一定的数论基础，可以问一下 deepseek
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
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;

const int N = 1e7 + 10;  // 扩大到1e7+10
const int mod = 1e9 + 7;

vector<ll> fac(N);      // 改用vector动态分配，避免栈溢出
vector<ll> invfac(N);

ll qmi(ll a, ll b) {
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

ll inv(ll x) { return qmi(x, mod - 2); }

// 初始化阶乘数组（优化计算方式）
void init() {
    fac[0] = invfac[0] = 1;
    for(int i = 1; i < N; i++) {  // 修正循环条件为 < N
        fac[i] = fac[i - 1] * i % mod;
    }
    // 一次性计算所有逆阶乘，更高效
    invfac[N-1] = inv(fac[N-1]);
    for(int i = N-2; i >= 0; i--) {
        invfac[i] = invfac[i + 1] * (i + 1) % mod;
    }
}

// 求组合数
ll C(ll n, ll m) {
    if(n < m || m < 0 || n >= N) return 0;
    return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}

void solve() {
    ll n, m;
    cin >> n >> m;
    if(n < 0 || m < 0 || n < m) {
        cout << 0 << endl;
        return;
    }
    cout << C(n, m) << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    init();
    
    int t; cin >> t;
    while(t--) solve();
    
    return 0;
}

组合数

image-20250402223308351

  • 可以抽象成背包然后优化，背包容量是b，有a个物品
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
#define ll long long
const int MOD = 1e9+7;
ll dp[3010];
int main()
{
    int a, b; cin >> a >> b;
    dp[0] = 1;
    for(int i = 1; i <= a; i++)
        for(int j = b; j >= 0; j--)
            dp[j] = (dp[j]+dp[j-1]) % MOD;
    cout << dp[b];
    return 0;
}