#include ＜cstdlib＞　　#include ＜iostream＞　　　　using namespace std;　　　　struct number　　{　　 int a;　　 int b;　　 };　　　　int main(int argc, char *argv[])　　{　　 int num,times,i;　　 number n[10];　　 cout＜＜"please input the times Andy built the hogpen(<=10):";　　 cin＞＞times;　　 　　 cout＜＜"please input the numbers of the hogpens(ai) and the remain pigs(bi):"＜＜endl;　　 for(i=0;i＜times;i++) cin＞＞n[i].a＞＞n[i].b;　　 i=0;num=n[0].a;　　 while(i＜times)　　 {　　 if(n[i].b==num%n[i].a) i++;　　 else{ if(i>0){num+=n[i-1].a;i=0;}else num++; }　　 }   cout＜＜"the number of pigs is:"＜＜num＜＜endl;　　 system("PAUSE");　　 return EXIT_SUCCESS;　　} 题目描述：猪的安家这道题目就是要求解模线性方程组。设 n=n1× n2×。。。×nk；m1=n/n1；m2=n/n2；。。。 mk=n/nk；由于mi与ni互质，即可以求解模线性方程。gcd(ni,mi) = ni×x ＋ mi×y=1 求出x和y，y即mi的负一次方；ans = (ans + M * y * A[i]) % n; ＃i nclude<string.h>＃i nclude<stdio.h> typedef long long i64; int num;i64 NN;i64 A[20],N[20]; void ext_euclid( i64 a, i64 b, i64 &x, i64 &y ){ i64 t, d; if (b == 0) { x = 1; y = 0; return; } ext_euclid( b, a%b, x, y ); t = x; x = y; y = t-a/b*y; return;} i64 China(){ i64 d, x, y, M, ans;  NN = 1; ans = 0; for (int i = 1;i <= num;i ++ )  NN *= N[i]; for (int i = 1;i <= num;i ++ ) {  M = NN /N[i];  ext_euclid( N[i], M, x, y );  ans = (ans + M * y * A[i]) % NN; } if (ans > 0) return(ans); else return(ans + NN);} int main(){ while (scanf("\n%d",&num) !=EOF) {  for (int i = 1;i <= num;i ++ )   scanf("\n%d %d",&N[i],&A[i]);  printf("%lld\n",China()); } return(0);}    /********************************************                     求解模线性方程   ax=b   (mod   n)   ,n>0                                           copyright   starfish                                                           2000/10/24         *********************************************/         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   less   than   zero!                       printf("The   %dth   answer   is   :   %ld\n",i+1,(e+i*(n/d))%n);             }     }             其中用到的ext_euclid   函数如下：         /*********************************************                 扩展欧几里德算法求gcd(a,b)=ax+by                                               copyright   starfish                                                           2000/10/24         *********************************************/         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;     }             ==========================================================     pascal语言的程序：     ==========================================================         {===   扩展的欧几里德算法，求出gcd(a,b)和满足gcd(a,b)=ax+by的整数x和y   ===}       function   extended_euclid(a,b:longint;var   x,y:longint):longint;     var     t:longint;     begin     if   b=0   then         begin         result:=a;         x:=1;         y:=0;       end     else       begin       result:=extended_euclid(b,a   mod   b,x,y);       t:=x;       x:=y;       y:=t-(a   div   b)*y;       end;     end;         {===   求解模线性方程   ax   ≡   b   (mod   n)   其中n>0   ===}     procedure   modular_linear_equation_solver(a,b,n:longint);     var     d,x,y,e,i:longint;     begin     d:=extended_euclid(a,n,x,y);     if   b   mod   d>0   then             writeln('No   answer!')     {输出无解信息}       else         begin             e:=x*(b   div   d)mod   n;           for   i:=0   to   d-1   do             writeln(   (e+i*(n   div   d))   mod   n   );   {输出第i个解   }         end;     end;           　　 　　

评论