#include <iostream> #include <cstdio> #include <algorithm> #include <vector> using namespace std; #define ll long long const int INF = 1e9; //裴蜀定理:若 ax + by = n 有解,则 gcd(a, b) | n //拓展欧几里得:求 ax + by = gcd(a, b) 的解,通过辗转相除法得到一组特解:x0 y0 // 得到 ax + by = c 的特解: // x = x0 * c / gcd(a, b) // y = y0 * c / gcd(a, b) // 通解: // X = x + b / gcd(a, b) * t // Y = y - a * gcd(a, b) * t (t = 0, 1, 2, 3 ...) //最小非零解: x = (x % b + b) % b // ax + by = gcd(a, b) // ax + by + k * ab - k * ak = gcd(a, b) // a(x + kb) + b(y - bk) = gcd(a, b) ----> x = (x % b + b) % b ll exgcd(ll a, ll b, ll &x, ll &y) { if(b == 0){//推理1,终止条件 x = 1; y = 0; return a; } ll r = exgcd(b, a%b, x, y); //先得到更底层的x2,y2,再根据计算好的x2,y2计算x1,y1。 //推理2,递推关系 ll t = y; y = x - (a/b) * y; x = t; return r; } void solve() { //ax同余1(mod prime) 求最小正整数解 ll a, b, x, y; scanf("%lld%lld", &a, &b); exgcd(a, b, x, y); printf("%lldn", (x % b + b) % b); } int main() { solve(); return 0; }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!