寒假第四讲

一.有理数取余

1.对应思路

该问题要求计算有理数 c=abc=b**a 对19260817取模的值。根据模运算的性质，这相当于求解方程 bx≡amod  19260817b**x≡amod19260817。解的存在性取决于 bb 是否存在模19260817的逆元。具体步骤如下：

  1. 大数取模：由于输入的 aa 和 bb 可能非常大（最多10001位），需要将这两个数转换为模19260817后的值。这可以通过逐位处理字符串并取模来实现。
  2. 判断逆元存在性：若 bb 模19260817的结果为0，则方程无解，直接输出“Angry!”。否则，利用费马小定理计算 bb 的逆元，因为19260817是质数。
  3. 计算最终结果：将 aa 的模值与逆元相乘后再次取模，得到最终结果。

2.对应代码

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

const int MOD = 19260817;

int mod(const string& s, int m) {
    int res = 0;
    for (char c : s) {
        res = (res * 10LL + (c - '0')) % m;
    }
    return res;
}

long long pow_mod(long long a, long long b, int mod) {
    long long res = 1;
    a %= mod;
    while (b > 0) {
        if (b % 2 == 1) res = (res * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return res;
}

int main() {
    string a_str, b_str;
    cin >> a_str >> b_str;

    int a_mod = mod(a_str, MOD);
    int b_mod = mod(b_str, MOD);

    if (b_mod == 0) {
        cout << "Angry!" << endl;
    } else {
        long long inv_b = pow_mod(b_mod, MOD - 2, MOD);
        long long ans = (a_mod * inv_b) % MOD;
        cout << ans << endl;
    }

    return 0;
}

3.学习总结

  1. 大数取模技巧：处理超大数时，可以通过逐位取模的方式避免数值溢出。例如，将字符串的每一位依次转换为当前结果的10倍加上该位数字，然后立即取模。
  2. 逆元计算：当模数为质数时，可以利用费马小定理快速计算逆元（即 ap−2mod  pa**p−2modp），时间复杂度为 O(log⁡p)O(logp)。
  3. 输入处理：注意输入的数值范围，使用字符串处理大数，并确保处理过程中不会溢出。
  4. 边界条件：题目保证输入的 aa 和 bb 不同时是模数的倍数，因此当 bb 的模为0时，直接判定无解。

该问题结合了数论中的模运算和逆元知识，同时考察了处理大数的技巧，综合应用了多种算法和编程技术。

二.Minimal Coprime

1.对应思路

对于每一个测试用例，我们需要找出区间 [l, r] 内所有的最小互质区间。由于我们要判断区间是否是最小互质，实际操作时可以考虑以下几点：

  1. 如果 l == r，那么只有一个单一的数，需要检查该数是否与自身互质，显然，对于任意数 a，gcd(a, a) ≠ 1，因此这类区间无法构成互质区间。
  2. 如果 l != r，则要判断区间 [l, r] 内每一个单元素子区间是否互质，同时对于更大的区间是否是最小互质区间。

2.代码

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<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e6 + 10,mod = 19260817,INT = 1e17,M = 5e6;
 
typedef pair<int,int> PII;
 
int qmi(int a,int k){
	int res = 1;
	while(k){
		if(k&1) res = res * a % mod;
		a = a * a % mod; 
		k >>= 1;
	}
	return res;
}
 
void slove(){
	string a,b;
	cin >> a >> b;
	int na = 0,nb = 0;
	for(auto c:a){
		na = (na * 10 + c - '0') % mod;
	}
	for(auto c:b) nb = (nb * 10 + c - '0') % mod;
	
	cout << na * qmi(nb,mod - 2) % mod << endl;
}
 
signed main()
{
	ios::sync_with_stdio(false);cin.tie(nullptr);
	int T = 1;
	while(T--) slove();
}

3.学习总结

最大公约数 (gcd)：在这道题中，我们频繁使用 gcd 来判断两个数是否互质。通过辗转相除法，可以有效地求出两个数的最大公约数，进而判断它们是否互质。

区间内互质判断：对于每一个子区间，需要检查它们是否互质，并且判断是否包含更小的互质子区间。这要求我们在求解时要小心处理每个区间，避免遗漏。

最小互质区间的判定：最小互质区间需要满足不包含任何其他互质区间，这一点是解题的关键。通过遍历区间的所有子区间，并确保它们不含更小的互质区间，可以确保找到所有最小互质区间。

优化：虽然本解法直接暴力枚举所有区间，但考虑到题目中区间范围较大，应该在实际使用中进行一些优化，如剪枝等策略。