求解单个同余方程的剩余系

 1 //ax ≡ b (mod n)
 2 #include <stdio.h>
 3 
 4 void gcd(int a,int b,int& d,int& x,int& y){
 5     if(!b){
 6         d = a; x = 1; y = 0;
 7     }else{
 8         gcd(b, a % b, d, y, x);
 9         y -= x * (a / b);
10     }
11 }
12 
13 void linear_mod_equation(int a,int b,int n,int& d,int sol[]){
14     // d = gcd(a,n)
15     int x,y;
16     gcd(a,n,d,x,y);
17     if(b % d) d = 0;
18     else{
19         sol[0] = x * (b / d) % n;
20         for(int i = 1; i < d; i++)
21             sol[i] = (sol[i - 1] + n / d) % n;
22     }
23 }
24 
25 int sol[1000];
26 int main(void){
27     int a,n,b,d;
28     scanf("%d%d%d",&a,&n,&b);
29     linear_mod_equation(a,b,n,d,sol);
30     for(int i = 0; i < d; i++)
31         printf("%d ",sol[i]);
32     printf("
");
33     return  0;
34 }