ACM复习（1）1077 韩信点兵

本文主要是介绍ACM复习（1）1077 韩信点兵，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

解题思路：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
上面的描述是《孙子算经》里面的一个题目，是不是和本题类似？
以前看过《孙子算经》的这个题目，知道了‘剩余定理’，那么这道题用剩余定理解决就行了

#include<stdio.h>
int main()
{long int a[8] , b[8];long long int n = 1, max = 0, key, flag = 0, total;for(int i = 0; i<8; i++){scanf("%ld", &a[i]);max = max > a[i] ? max : a[i];// 观察后发现《孙子算经》或者题目中出现的除数都是质数，直接相乘即为最小公倍数n *= a[i];}for(int i = 0; i<8; i++)scanf("%ld", &b[i]);for(int i = 0; i<8; i++)for(int j = 1; ;j++){// n除去a[i]可得其他除数的最小公倍数key = j * n / a[i];if(key % a[i] == 1){flag += key * b[i];break;}}total = flag % n;printf("%lld\n",total < max ? total + n : total);
}