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=y2y=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==1LL 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 localfreopen("data.txt","r",stdin);#endifwork();return 0;}
View Code
