转自：
C++循环结构设计——韩信点兵_c++韩信点兵_LS_FIGHTING的博客-CSDN博客
韩信点兵(hanxin)
相传韩信才智过人，从不直接清点自己军队的人数，只要让士兵先后以三人一排、五人一排、七人一排地变换队形，而他每次只掠一眼队伍的排尾就知道总人数了。输入包含多组数据，每组数据包含3个整数a,b,c，表示每种队形排尾的人数(a<3,b<5,c<7)，输出总人数的最小值(或报告无解)。已知总人数不小于10，不超过100。输入到文件结束为止。
样例输入：
2 1 6
2 1 3
样例输出：
Case 1： 41
Case 2： No answer
方法一：已知总人数不小于10，不超过100，则在此范围内使用for循环依次检验总人数所排队型是否满足队尾人数。
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int sum=0,a,b,c;
int kcase=1;
while(scanf(“%d%d%d”,&a,&b,&c)==3)
{
for(sum=10;sum<=100;sum++)
{
if(sum%3==a&&sum%5==b&&sum%7==c)
{
printf(“Case %d: %d\n”,kcase++,sum);
break;
}
}
if(sum==101)
{
kcase++;
printf(“No answer\n”);
}
}
return 0;
}
方法二：中国剩余定理，又称为中国余数定理、孙子剩余定理，古有”韩信点兵”、”孙子定理”、”鬼谷算”、”隔墙算”、”剪管术”、”秦王暗点兵”、”物不知数”之名，是数论中的一个重要命题。
在中国古代著名数学著作《孙子算经》中，有一道题目叫做“物不知数”，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。
中国数学家秦九韶于1247年做出了完整的解答，口诀如下：
三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五使得知
这个解法实际上是，首先利用秦九韶发明的大衍求一术求出
5和7的最小公倍数35的倍数中除以3余1的最小一个为70（这个称为35相对于3的数论倒数），
3和7的最小公倍数21（除以5余1）相对于5的数论倒数21，
3和5的最小公倍数15（除以7余1）相对于7的数论倒数15。
然后70×2+21×3+15×2=233，233便是可能的解之一。
它加减3、5、7的最小公倍数105的若干倍仍然是解，因此最小的解为233除以105的余数23。
附注：这个解法并非最简，因为实际上35就符合除3余2的特性，所以最小解是：35×1+21×3+15×2-3×5×7=128-105=23
最小解加上105(=3×5×7)的正整数倍都是解
物不知数”的解法实际上给出了求解一般同余方程组的方法。
设m1，m2，…，mi为两两互质的正整数，a1，a2，…，ak为任意整数，则同余方程组：
x≡a1(mod m1)；
x≡a2(mod m2)；
……
x≡ai(mod mi)；
总有整数解，并且它的全部解可模仿上述方法得到。
#include <iostream>
#include <stdio.h>
using namespace std;
int main()
{
int a,b,c;
int kcase=1;
while(scanf(“%d %d %d”,&a,&b,&c)!=EOF)
{
int s = a*70+b*21+c*15;
s%=(3*5*7);
if(s>100||s<10)
{
kcase++;
printf(“No answer\n”);
}
else
{
printf(“Case %d: %d\n”,kcase++,s);
}
}
return 0;
}
————————————————
版权声明：本文为CSDN博主「LS_FIGHTING」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/LEE_FIGHTING_JINGYU/article/details/79948988