拓展欧几里得

#include <iostream> #include <cstring> #include <cstdio> typedef long long ll; using namespace std; void ExGcd(ll a,ll b,ll &gcd,ll &x,ll &y){ //拓展欧几里得解 Ax + By = gcd(A,B) if(b == 0){ x = 1; y = 0; gcd = a; } else { ExGcd(b,a%b,gcd,y,x); y -= (a/b) * x; //根据公式推出 x1 = y2; y1 = x2 - (a/b) * y2; // ll temp = x; // x = y; // y = temp - (a/b)*y; } } int main(){ ll A,B,p,x,y,gcd; // Ax + By = p; 求解 x,y scanf("%lld%lld%lld",&A,&B,&p); ExGcd(A,B,gcd,x,y); // ExGcd(B,A%B,gcd,y,x); //交换 x , y 与上一句相等价 if(p % gcd != 0){ //无解 printf("No....\n"); } else { x *= p/gcd; y = (p - A*x)/B; printf("%lld %lld\n",x,y); } return 0; }

上面求出的只是 Ax + By = p 众多解中的一个，可能是负的，但有时由于题中的各种限制，需要求出x的最小正整数解。 根据 Ax + By = p 的通解公式 x = (x + k * (B / gcd(A,B) ) * p / gcd(A,B) 设 t = B / gcd(A,B) 则 x 的最小正整数解为 (x % t + t) % t; 由于gcd(A,B) 可能为负，所以t也可能为负，所以要先特判一下 if(t < 0) t = -t;

#include <iostream> #include <cstring> #include <cstdio> typedef long long ll; using namespace std; void ExGcd(ll a,ll b,ll &gcd,ll &x,ll &y){ //拓展欧几里得解 Ax + By = gcd(A,B) if(b == 0){ x = 1; y = 0; gcd = a; } else { ExGcd(b,a%b,gcd,y,x); y -= (a/b) * x; //根据公式推出 x1 = y2; y1 = x2 - (a/b) * y2; } } int main(){ ll A,B,p,x,y,gcd; // Ax + By = p; 求解 x,y scanf("%lld%lld%lld",&A,&B,&p); ExGcd(A,B,gcd,x,y); // ExGcd(B,A%B,gcd,y,x); //交换 x , y 与上一句相等价 if(p % gcd != 0){ //无解 printf("No....\n"); } else { x *= p/gcd; ll t = B/gcd; //x要加的B/gcd if(t < 0) //当gcd为负时，t可能为负 t = -t; x = (x%t + t)%t; //x的最小正整数解 y = (p - A*x)/B; printf("%lld %lld\n",x,y); } return 0; }

学习博客：https://blog.csdn.net/sdutstudent/article/details/78795643