（数论）51NOD 1079 中国剩余定理

一个正整数K，给出K Mod 一些质数的结果，求符合条件的最小的K。例如，K % 2 = 1, K % 3 = 2, K % 5 = 3。符合条件的最小的K = 23。

Input

第1行：1个数N表示后面输入的质数及模的数量。（2 <= N <= 10)

第2 - N + 1行，每行2个数P和M，中间用空格分隔，P是质数，M是K % P的结果。（2 <= P <= 100, 0 <= K < P)

Output

输出符合条件的最小的K。数据中所有K均小于10^9。

Input示例

Output示例

23

解：
方法一

 #include <stdio.h>

 typedef struct

 {

     int p, m;

 }str;

 str s[];

 int cmp(const void *a, const void *b)

 {

     return ((str *)a)->p > ((str *)b)->p ? - : ;

 }

 int main()

 {

     int n;

     while (scanf_s("%d", &n) != EOF)

     {

         long long mult = ;

         int ans;

         for (int i = ; i < n; i++)

         {

             scanf_s("%d%d", &s[i].p, &s[i].m);

             mult *= s[i].p;

         }

         qsort(s, n, sizeof(str), cmp);

         for (int i = , flag = ; flag && i * s[].p <= mult; i++)

         {

             ans = s[].p * i + s[].m;

             for (int j = ; ans % s[j].p == s[j].m;j++)

             {

                 if (j == n - )

                 {

                     flag = ;

                     break;

                 }

             }

         }

         printf("%d\n", ans);

     }

 }

改进法一后的法二：

 #include <stdio.h>

 int main()

 {

     int n;

     while (scanf_s("%d", &n) != EOF)

     {

         int a, b, c, d;

         scanf_s("%d%d", &a, &b);

         for (int i = ,j; i < n; i++)

         {

             scanf_s("%d%d", &c, &d);

             for (j = ; (a * j + b) % c != d; j++);

             b = a * j + b;

             a *= c;

         }

         printf("%d\n", b);

     }

 }

法三：

中国剩余定理（https://baike.baidu.com/item/孙子定理/2841597?fromtitle=%E4%B8%AD%E5%9B%BD%E5%89%A9%E4%BD%99%E5%AE%9A%E7%90%86&fromid=11200132&fr=aladdin）+ 拓展欧几里得

（注意中国剩余定理必满足使用拓展欧几里得求逆元的条件，即n个不同质数，其中n-1个的乘积必与剩下的1个互质）

 #include <stdio.h>

 int inv[], pm[];

 void Ex_gcd(int a, int b, int *x, int *y);

 int main()

 {

     int t;

     while (scanf_s("%d", &t) != EOF)

     {

         long long M = , ans = ;

         for (int i = ; i < t; i++)

         {

             scanf_s("%d%d", &pm[i], &pm[i + ]);

             M *= pm[i];

         }

         for (int i = , temp; i < t; i++)

         {

             Ex_gcd(M / pm[i], pm[i], &inv[i], &temp);

             inv[i] = (inv[i] + pm[i]) % pm[i];

             ans = (ans + M / pm[i] * inv[i] * pm[i + ]) % M;

         }

         printf("%d\n", ans);

     }

 }

 void Ex_gcd(int a, int b, int *x, int *y)

 {

     if (b == )

     {

         *x = ;

         *y = ;

         return;

     }

     Ex_gcd(b, a%b, x, y);       //或者可以这么写

     int t = *y;                 //ex_gcd(b, a%b, y, x); 
     *y = *x - a / b * (*y);     //*y = *y - (a / b)**x;

     *x = t;                     //return;

     return;

 }

巴特西

（数论）51NOD 1079 中国剩余定理

最新文章

热门文章