#《算法竞赛入门经典》题解（选讲） 一、韩信点兵（1） #include <stdio.h> // C语言描述
int main(){ int i , a , b , c , t = 1; while(scanf("%d %d %d",&a,&b,&c) != EOF){ int flag = 0; for(i = 10;i <= 100;i++){ if(i %3 == a && i %5 == b && i %7 == c){ flag = 1; printf(“case %d: %d\n”,t++,i); break; } } if(!flag) printf(“case %d: No answer\n”,t++); } return 0; } 讲解：就是一个普通的遍历，但是这样暴力的方法不是我们算法的初衷，经过查阅资料，我们来分析下面这种算法
韩信点兵：优化 我们先来介绍一下“中国剩余定理” 我国古代数学名著《孙子算经》载有一道数学问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”这里的几何指多少的意思。翻译成数学语言就是：求正整数N，使N除以3余2，除以5余3，除以7余2。（有关同余方程式的问题我就不说了，多年前的数竞党，遮脸ing，都不记得了） 3 ,5 ,7实际上对应着三个数，分别对应70，21，15，那么这些数到底是有什么样的特点呢？ 70 %3 = 1 && 70 %5 = 0 && 70 %7 = 0；（270 满足除3余2且被5,7整除） 21 %5 = 1 && 21 %3 = 0 && 21 %7 = 0；（321满足除5余3且被3,7整除） 15 %7 = 1 && 15 %5 = 0 &&15 %3 = 0；（15*2满足除7余2且被3,5整除） 对应加和：N = 2×70 + 3×21 + 2×15；（N是满足同余房程的一个解！） 但是怎么样才能是最小解呢？ 我们来看3 ，5 ，7的最小公倍数lcm = 3×5×7 = 105； 由基本的数论知识我们知道最小解ans满足ans + lcm×k会满足本题条件，所以我们只需要用N %lcm就会是最终的答案！
那我们如何使用中国剩余定理来处理韩信点兵的问题呢？ #include <stdio.h>
int main(){ int i , a , b , c , t = 1; while(scanf("%d %d %d",&a,&b,&c) != EOF){ int ans = a70 + b21 + c*15; if((ans 5) >= 10 && (ans 5) <= 100) printf(“case %d: %d\n”,t++,ans5); else printf(“case %d: No answer\n”,t++); } return 0; }
在下一期的韩信点兵（2）中我们将详细讲解中国剩余定理在算法竞赛中的应用！
