50tps
直接按照
进行枚举
60tps
先化简式子
然后直接从 开始枚举 ，直到满足条件输出。
或者直接推成最简带模数学式 即
枚举 也是一样的；
#include <bits/stdc++.h>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
for (long long i = 1;; i++) {
if ((a * i) % b == 1 或者 a * i - (((a * i) / b) * b) == 1) {
cout << i << endl;
return 0;
}
}
}
100 tps
记原方程 为方程 1
结论1.1: (a, b)=1 由题意得：
令 ,则有:
又 ，我们得到:
结论1.2: 假设该命题不成立，我们有:
此时就有矛盾出现，根据最大公约数的定义，代入可得:
又有 为 的最大公约数。所以矛盾，即证
结论 注意一除法横式:
易得：
注意到:
即证
结论2.1，欧几里得算法:
设 ,我们可以的到两个引理。
引理1:
设 ,我们有:
又 , 设 同结论 1.2 , 则有:
即证 引理2: 由 可知，此处不再细讲。 综上所述，我们有:
回到结论1.3:
设有一组 满足欧拉算法，易得:
应满足:
我们有:
于是:
可求得一组解:
扩展欧几里德算法是用来在已知 求解一组 ，使它们满足贝祖等式： (解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。
刚才的讲解已经比较清楚了，接下来我们来理一下解题思路:
- 特殊情况: ，此时令 即可
- 递归调用 函数，求得
- 求解 ，函数结束。
- 处理 为负数的问题。
#include <bits/stdc++.h>
using namespace std;
void exgcd(long long a, long long b, long long &x, long long &y) {
if (!b) {
x = 1;
return;
}
exgcd(b, a % b, x, y);
long long t = x;
x = y;
y = t - (a / b) * y;
return;
}
int main() {
long long a, b, x, y;
cin >> a >> b;
exgcd(a, b, x, y);
cout << (x % b + b) % b;
}