首页 > 代码库 > POJ 1006 中国剩余定理

POJ 1006 中国剩余定理

2024-07-11 19:09:05   230人阅读

【题意】：

给定p，e，i，d，求解

(x + d) % 23 = p 
(x + d) % 28 = e
(x + d) % 33 = i

x最小正整数值

【知识点】：

中国剩余定理

【题解】：

典型的 xmodmi = ai模型，其中mi间两两互素。但该题式子较少，也可以直接自己化简带入值。

【代码】：

 1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector>10 #include <cstring>11 #include <sstream>12 #include <iostream>13 #include <algorithm>14 #include <bitset>15 #include <climits>16 #include <complex>17 using namespace std;18 19 #define wh while20 #define inf (int)(~0u/2)21 #define FOR(i, n) for(int i = 0; i < n; i++)22 #define FOR1(i, n) for(int i = 1; i < n; i++)23 #define FOR2(i, n) for(int i = 0; i <= n; i++)24 #define REP(i,n) for(int i = 1; i <= n; i++)25 #define FORI(it,n) for(typeof(n.begin()) it = n.begin(); it != n.end(); it++)26 #define sf scanf27 #define pf printf28 #define frs first29 #define sec second30 #define psh push_back31 #define mkp make_pair32 #define PB(x) push_back(x)33 #define MP(x, y) make_pair(x, y)34 #define clr(abc,z) memset(abc,z,sizeof(abc))35 #define lt(v) v << 136 #define rt(v) v << 1 | 137 #define mid ((l + r) >> 1)38 #define lson l, mid, v << 139 #define rson mid + 1, r, v << 1 | 140 #define fre freopen("1.txt", "r", stdin)41 42 typedef long long LL;43 typedef long double LD;44 45 LL exgcd(LL a, LL b, LL& x, LL& y){46     if(b == 0){47         x = 1; y = 0; return a;48     }49     else{50         LL r = exgcd(b, a % b, y, x);51         y -= x * (a / b);52         return r;53     }54 }55 56 int chinese(int a[], int m[], int n){57     int M = 1, ret = 0;58     for(int i = 0; i < n; i++) M *= m[i];59     for(int i = 0; i < n; i++){60         LL x, y;61         int ta = M / m[i], tb = m[i];62         exgcd(ta, tb, x, y);63         ret = (ret + ta * x * a[i]) % M;64     }65     return (ret + M) % M;66 }67 68 int main(){69     int p, e, i, d, it = 0;70     while(sf("%d%d%d%d", &p, &e, &i, &d) != EOF){71         if(p == -1 && e == -1 && i == -1 && d == -1) break;72         int a[] = {p, e, i}, m[] = {23, 28, 33};73         int ans = chinese(a, m, 3);74         ans = (ans - d + 21252) % 21252;75         if(ans == 0) ans = 21252;76         pf("Case %d: the next triple peak occurs in %d days.\n", ++it, ans);77     }78 }

 


联系
我们