poj 1005 Biorhythms(孫の定理、余定理を求める)

1970 ワード

大体の問題:
この問題はPOJに訳文がある(原文右上隅)
 
問題解決の考え方:
中国の残りの定理、本題の難点はプログラミングではありませんて、テーマを分析してそして数学の公式に転化します
本題の解法を導入するには,まず一つの物語を見てみよう. 「韓信点兵」:      伝説によると、西漢大将の韓信は、比較的若いため、彼の部下は彼に感心しなかった.ある閲兵式の時、韓信は兵士に3つの縦隊に分けるように要求したが、結局末尾は2人増え、5つの縦隊に変わった.結局末尾は3人増え、7つの縦隊に変わった.結果は2人残った.その後、下級将校から兵士2395人が報告された.だから韓信は23128233、------によって、隣接する2つの数の間隔は105(3、5、7の最小公倍数)で、直ちに実際の人数は2333人(2333=128+20のため)であるべきだと言いましたχ105+105、それは3余り2で除算して、5余り3で除算して、7余り2で除算します).このように下級将校を敬服させたのが、韓信の点兵の話だ.   
 韓信の点兵問題の簡略化:既知 n%3=2,  n%5=3,  n%7=2,  nを求める. 
  私たちのこの問題を見て、p,e,i,dを読みます. 4個の整数
既知(n+d)%23=p;   (n+d)%28=e;   (n+d)%33=i ,nを求める . 
 
二つの問題は同じです.しかし、韓信は当時結果を計算したのだろうか.   韓信用は「中国の残りの定理」であり、「孫算経」には計算方法があり、関連資料を調べることができる.  「韓信点兵」問題は以下のように計算される. 
n%3=2,n%5=3,n%7=2,3,5,7互質 (互質はこの3つの数の最小公倍数を直接得ることができる)
x=n%3=2,y=n%5=3,z=n%7=2      5×7×a被3除余1,有35×2=70、すなわちa=2;         3×7×b被5除余1,用21×1=21、すなわちb=1;         3×5×c 7で残り1を除去し、15×1=15、すなわちc=1.  ではn=(70)×x+21×y+15×z)%lcm(3,5,7)=23これはnの最小解である.
 韓信は兵士数が2300~2400人であることが知られているので、n+iしか必要ありません.×lcm(3,5,7)は2333を得,このときi=22
同じように、この問題の解法は次のとおりです. 
既知(n+d)%23=p;   (n+d)%28=e;   (n+d)%33=i         33×28×a 23で残り1を除去し、33で×28×8=5544;         23×33×b 28で残り1を除去し、23×33×19=14421;         23×28×c 33で残り1を除去し、23で×28×2=1288.        したがって(5544)×p+14421×e+1288×i)% lcm(23,28,33) =n+d 
また、lcm(23,28,33)=21252である23,28,33の相互作用.      だからn=(5544)×p+14421×e+1288×i-d)%21252
本題で求めたのは最小整数解であり,nが負であることを避けるため,最終結果はn=[n+21252]%21252であり,最終的にnを解く式は以下の通りである.
n=(5544*p+14421*e+1288*i-d+21252)%21252;
#include"stdio.h"
int main()
{
	int p,e,i,d;
	int ans,cnt;
	cnt=0;
	while(scanf("%d%d%d%d",&p,&e,&i,&d)!=-1)
	{
		if(p==-1&&e==-1&&e==-1&&d==-1)
			break;
		cnt++;
		ans=(5544*p+14421*e+1288*i-d+21252)%21252;
		if(ans==0)ans=21252;
		printf("Case %d: the next triple peak occurs in %d days.
",cnt,ans); } return 0; }