中国剩余定理

2019-04-13 16:24发布

站内文章 / 模拟电子
17508 0 987
中国剩余定理用于求解多个模方程的解，即:x = a[i] mod(b[i])（其中b[i]要求两两互质）；类似于韩信点兵类的问题。 令N = b[0]*b[1]*b[2].....b[n]; 则在模N的剩余系中，方程有唯一解。 中国剩余定理模板题目poj1006; #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long #define MAX 1000 #define INF INT_MAX #define eps 1e-6 using namespace std; void ex_gcd(ll a, ll b, ll& x, ll& y){ //扩展的欧几里得算法求模方程的一个解x if (b == 0){ x = 1; y = 0; return; } ex_gcd(b, a%b, y,x); y -= x * (a / b); } ll a[10],d; ll b[] = {23,28,33}; ll china(int n){ //中国剩余定理，求最小整数解 ans = (ans + N) % N(模N下的唯一解)； ll N = 1; ll ans = 0; for (int i=0; i 0) return ans - d; else return ans - d + N; } int main(){ int cas = 0; while (scanf("%lld%lld%lld%lld",&a[0],&a[1],&a[2],&d) && d >= 0){ cas++; printf("Case %d: the next triple peak occurs in %lld days. ",cas,china(3)); } return 0; }

热门文章