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;
この問題は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;
}