解模线性方程ax=b(mod n).cpp

acm中各种代码

 #include<stdio.h>
  int    ext_euclid(int    a,int    b,int    &x,int    &y)   
   {   
         int    t,d;   
         if    (b==0){
    x=1;
    y=0;
    return    a;
}   
         d=ext_euclid(b,a%b,x,y);   
         t=x;   
         x=y;   
         y=t-a/b*y;   
         return    d;   
   }    
    
   /********************************************   
    
               求解模线性方程    ax=b    (mod    n)    ,n>0   
    
   *********************************************/   
    
   void    modular_linear_equation_solver(int    a,int    b,int    n)   
   {   
         int    e,i,d;   
         int    x,y;   
         d = ext_euclid(a,n,x,y);   
         if(b%d>0)    printf("No    answer!\n");   
               else   
                     {     
                           e=(x*(b/d))%n;   
                           for    (i=0;i<d;i++)      //notice!    here    x    maybe    <0   
                           printf("The %dth answer is:%ld\n",i+1,(e+i*(n/d))%n);     
                           }   
         }  

int main()
{
    int a,b,n;
    while(scanf("%d %d %d",&a,&b,&n) != EOF)
    modular_linear_equation_solver(a,b,n); 
    return 0;   
}