韓信點(diǎn)兵是如何計(jì)算的?
相傳韓信才智過人,從不直接清點(diǎn)自己軍隊(duì)的人數(shù),只要讓士兵先后以三人一排、五人一排、七人一排地變換隊(duì)形,而他每次只掠一眼隊(duì)伍的排尾就知道總?cè)藬?shù)了。輸入3個(gè)非負(fù)整數(shù)a,b,c ,表示每種隊(duì)形排尾的人數(shù)(a<3,b<5,c<7),輸出總?cè)藬?shù)的最小值(或報(bào)告無解)。已知總?cè)藬?shù)不小于10,不超過100 。
輸入
輸入3個(gè)非負(fù)整數(shù)a,b,c ,表示每種隊(duì)形排尾的人數(shù)(a<3,b<5,c<7)。例如,輸入:2 4 5
輸出
輸出總?cè)藬?shù)的最小值(或報(bào)告無解,即輸出Noanswer)。實(shí)例,輸出:89
樣例輸入
2 1 6
樣例輸出
41
定理1 如a被n除所得的余數(shù)等b被n除所得的余數(shù),c被n除所得的余數(shù)等于d被n除所得的余數(shù), 則ac被n除所得的余數(shù)等于b d被n除所得的余數(shù)。
用同余式敘述就是:
如a≡b(mod n ),c≡d(mod n )
則ac≡b d(mod n )
定理2 被除數(shù)a加上或減去除數(shù)b的倍數(shù),再除以b,余數(shù)r不變。即
如a ≡ r(mod b ),則a ± b n≡r(mod b )
例如70≡1(mod 3 )可得70±10×3≡1(mod 3 )
【韓信點(diǎn)兵法口訣的原理】
①能被5,7除盡數(shù)是35k,其中k=2,即70除3正好余1,70a 除3正好余a。
②能被3,7除盡數(shù)是21k,其中k=1,即21除5正好余1,21b 除5正好余b。
③能被3,5除盡數(shù)是15k,其中k=1,即15除7正好余1,15c 除7正好余c。
這樣——
根據(jù)①可知 70a+21b+15c 除3正好余a。
根據(jù)②可知 70a+21b+15c 除5正好余b。
根據(jù)③可知 70a+21b+15c 除7正好余c。
(70a+21b+15c)%(3*5*7)為最小值,然后再判斷最小值是否滿足條件。
復(fù)制代碼
1 #include <stdio.h>
2
3 int main(){
4 int a;
5 int b;
6 int c;
7 int result;
8
9 scanf("%d%d%d",&a,&b,&c);
10 result=(70*a+21*b+15*c)%(3*5*7);
11
12 if(result>=10 && result<=100)
13 printf("%d\n",result);
14
15 else
16 printf("No answer\n");
17
18 return 0;
19 }