解模线性方程ax=b(modn)

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 using namespace std;
 5 typedef long long LL;
 6 // 求x和y使得ax+by=d并且|x|+|y|最小。其中d=gcd(a,b)
 7 void exgcd(LL a,LL b,LL& d,LL& x,LL& y){
 8     if(!b) d = a,x = 1,y = 0;
 9     else{
10         exgcd(b,a % b,d,y,x);
11         y -= x * (a / b);
12     }
13 }
14 // 用扩展欧几里得解模线性方程 ax=b(mod n)
15 bool modular_Linear_Equation(LL a,LL b,LL n){
16     LL x,y,x0,i,d;
17     exgcd(a,n,d,x,y);
18     if(b % d) return false; //d不是b的约数时没有解
19         x0 = x * (b / d) % n; // 得到一个特解
20     for(i = 1 ; i <= d ; i++)
21        printf("%d
",(x0 + i * (n / d)) % n); // 恰好有d个解
22     return true;
23 }
24 int main(){
25     modular_Linear_Equation(3,6,6);
26     return 0;
27 }