定理：对于整数方程ax + by = c，若c mod Gcd(a, b) == 0，则该方程存在整数解，否则不存在整数解。
设d = gcd(a,b), a' = a/d, b' = b/d, 则方程变形为 d(a'x + b'y) = c 若方程有整数解，则 d|c, 否则无解. 设c' = c/d, 则方程 ax + by = c等价于 a'x + b'y = c' 因为gcd(a',b') = 1, 则我们可以求得 a'x + b'y = gcd(a',b') = 1 的解，
即 ax + by = gcd(a,b) = d的解 x，y。 则c'x, c'y就是 ax + by = c 的一组解。 xx = c'x + b't, yy = c'y - a't t∈Z就是所有满足条件的解。
#include<cstdio> int x,y,a,b,c; int extended_euclid(int a,int b,int &x,int &y) { if(b==0) //即gcd(a,b)=a { x=1;y=0; return a; } int n=extended_euclid(b,a%b,x,y); //最大公约数相等 int k=x; x=y; y=k-a/b*y; return n; } bool kk(int a,int b,int c,int &x,int &y) //ax+by=c { int n=extended_euclid(a,b,x,y); if(c%n) return 0; //c不是最大公约数时无解 int k=c/n; x*=k;y*=k; return 1; } int main() { scanf("%d%d%d",&a,&b,&c); if(!kk(a,b,c,x,y)) printf("Impossible\n"); else printf("x=%d y=%d\n",x,y); return 0; }之前的是摘抄，下面都是自己的感悟： 求解方程 a*x ≡ b (mod n)
ð a*x – y*n = b,这个就是二元一次方程组，用扩欧
ð 如果方程有解，则b%(gcd(a,b))==0，如果不为0，则代表无解
ð 否则用扩欧(a,n,x,y);,解出一组x,y 代表a*x – y*n = b
下面给出一份求解a*x ≡ 1 (mod b) 的最小整数解的代码
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int ex1 (int a,int b,int &x,int &y)
{
if (b == 0)
{
x = 1,y = 0;
return a;
}
else
{
int gcd1 = ex1(b,a%b,x,y);//
int k = x;
x = y;
y = k-(a/b)*y;
return gcd1;
}
}
int main ()
{
int a,b,x,y;
cin >>a>>b;
int ans = ex1 (a,b,x,y);
if (1%ans!=0)cout <<"No answer"<<endl;
else
{
x = x%b;
while (x<0)x+=b;
cout <<x<<endl;
}
return 0;
}
