韩信点兵中国剩余定理

1077 韩信点兵

时间限制:500MS 内存限制:65536K
提交次数:1103 通过次数:99

题型: 编程题语言: G++;GCC

Description

相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人、 17人一列余2人、19人一列余10人、23人一列余1人、29人一列余11人。

刘邦茫然而不知其数。你呢？你是一位优秀的程序员，请你帮刘邦解决这一问题。

输入格式

要求由键盘输入A,B,C,D,E,F,G,H,a,b,c,d,e,f,g,h十六个数，分别代表每A人一列余a、每B人一列余b、每C人一列余c、每D人一列余D、每E人一列余e、每F人一列余f、每G人一列余g、每H人一列余h，其中A,B,C,D,E,F,G,H为互不相等的质数

输出格式

输出总兵士数，要求输出满足条件的最小的一个，但要满足8种排法的每一种排法至少可排一列。（保证给的数据，有结果且计算的结果不会超过2的63次方）

输入样例

2 3 5 7 11 13 17 19

1 1 1 1 1 1 1 1

输出样例

9699691

中国剩余定理（CRT）的表述如下

设正整数两两互素，则同余方程组

有整数解。并且在模下的解是唯一的，解为

其中，而为模的逆元。

中国剩余定理：

先考虑这样一个问题：

X % 3 = 2

X % 5 = 3

X % 7 = 2

minans = 23

怎么做呢？可以先把除以3余数是2的数字先写出来：2 5 8 ....

再把除以5余数是3的写出来 3、8、....

那么共同的数字是8,所以8就是除以3余2且除以5余3的最小数字。。

中国剩余定理也是类似的思想

对于每条等式，都找出一个val，使得val % mod[i] = r[i]且 val % 其他数字是等于0的

第一条式子，这个val = 140

关于怎么找每条式子的val，可以想到用逆元，先解出t % mod[i] = 1，再把r[i] * t即是val。因为这个时候余数就是r[i]了，

r[i] * t % mod[i] = ((r[i] % mod[i]) * (t % mod[i])) % mod[i] = r[i]

下面来讨论下为什么要val % 其他数字是等于0的。

这里是根据余数的性质，

上面的式子，val分别是140、63、30

把他们加起来 % (mod[1] * mod[2] * ..... *mod[n])是答案。

先求解前两个的答案，就是先满足除以3余2，除以5余3的数。

ans = (140 + 63) % 15

这里的140满足%3 = 2而且%其他数字 = 0

这样的好处是不会相互影响。

满足一个等式，而不会影响另一个等式

注意这里要满足必须排至少一列，暴力特判就好了

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
LL exgcd (LL a,LL mod,LL &x,LL &y) {
    //求解a关于mod的逆元     ★：当且仅当a和mod互质才有用
    if (mod==0) {
        x=1;
        y=0;
        return a;//保留基本功能，返回最大公约数
    }
    LL g=exgcd(mod,a%mod,x,y);
    LL t=x;    //这里根据mod==0  return回来后，
    x=y;    //x,y是最新的值x2,y2,改变一下，这样赋值就是为了x1=y2
    y=t-(a/mod)*y;    // y1=x2(变成了t)-[a/mod]y2;
    return g;            //保留基本功能，返回最大公约数
}
LL get_inv(LL a,LL MOD) //求逆元。记得要a和MOD互质才有逆元的
{
    LL x,y;  //求a关于MOD的逆元，就是得到的k值是a*k%MOD==1
    LL GCD=exgcd(a,MOD,x,y);
    if (GCD==1)//互质才有逆元可说
        return (x%MOD+MOD)%MOD;//防止是负数
    else return -1;//不存在
}
const int maxn = 100;
LL r[maxn], mod[maxn];
LL CRT(LL r[], LL mod[], int n) { // X % mod[i] = r[i]
    LL M = 1;
    LL ans = 0;
    for (int i = 1; i <= n; ++i) M *= mod[i];
//    cout << M << endl;
    for (int i = 1; i <= n; ++i) {
        LL MI = M / mod[i]; //排除这个数
        ans += r[i] * (MI * get_inv(MI, mod[i])); //使得MI % mod[i] = 1
//        cout << get_inv(MI, mod[i]) << endl;
        ans %= M;
    }
//    if (ans < 0) ans += M;
    while (true) {
        int i;
        for (i = 1; i <= n; ++i) {
            if (ans < mod[i]) {
                ans += M;
                break;
            }
        }
        if (i == n + 1) return ans;
    }
    return ans;
}
void work() {
    int n = 8;
    for (int i = 1; i <= n; ++i) cin >> mod[i];
    for (int i = 1; i <= n; ++i) cin >> r[i];
    cout << CRT(r, mod, n) << endl;
}
int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    work();
    return 0;
}

View Code

韩信点兵 中国剩余定理

韩信点兵中国剩余定理