扩展欧几里得与中国剩余定理

扩展欧几里得 中国剩余定理 BYC Swimmy 准备知识 同余两个整数a b 若它们除以整数m所得的余数相等 则称a b对于模m同余记作a b modm 读作a同余于b模m 或读作a与b关于模m同余 比如26 14 mod12 同余的性质 性质1反身性a a modm 2对称性若a b modm 则b a modm 3传递性若a b modm b c modm 则a c modm 4同余式相加若a b modm c d modm 则a c b d modm 5同余式相乘若a b modm c d modm 则ac bd modm 线性组合 线性组合是一个线性代数中的概念 代表一些抽象的向量各自乘上一个标量后再相加 欧几里得算法 欧几里德算法又称辗转相除法 用于计算两个正整数a b的最大公约数 其计算原理依赖于下面的定理 定理 gcd a b gcd b amodb a b且amodb不为0 证明 a可以表示成a kb r 则r amodb假设d是a b的一个公约数 则有d a d b 而r a kb 因此d r因此d也是 b amodb 的公约数因此 a b 和 b amodb 的公约数是一样的 其最大公约数也必然相等 得证 乘法逆元 例如 4关于模7的乘法逆元为多少 4 X 1 mod7 这个方程等价于求一个X和K 满足4X 7K 1其中X和K都是整数 若ax 1modf则称a关于模f的乘法逆元为x 也可表示为ax 1 modf 当a与f互素时 a关于模f的乘法逆元有唯一解 如果不互素 则无解 如果f为素数 则从1到f 1的任意数都与f互素 即在1到f 1之间都恰好有一个关于模f的乘法逆元 例如 求5关于模14的乘法逆元 14 5 2 45 4 1说明5与14互素 存在5关于14的乘法逆元 1 5 4 5 14 5 2 5 3 14因此 5关于模14的乘法逆元为3 其求法可用欧几里德算法ExtendedEuclid d f 算法求d关于模f的乘法逆元d 1 即d d 1modf 1 1 X1 X2 X3 1 0 f Y1 Y2 Y3 0 1 d 2 if Y3 0 thenreturnd 1 null 无逆元3 if Y3 1 thenreturnd 1 Y2 Y2为逆元4 Q X3divY3 整除5 T1 T2 T3 X1 Q Y1 X2 Q Y2 X3 Q Y3 6 X1 X2 X3 Y1 Y2 Y3 7 Y1 Y2 Y3 T1 T2 T3 8 goto2 扩展欧几里德定理 对于不完全为0的非负整数a b gcd a b 表示a b的最大公约数 必然在存整数对x y 使得gcd a b ax by 求解x y的方法的理解设a b 1 显然当b 0 gcd a b a 此时x 1 y 0 2 ab0时设ax1 by1 gcd a b bx2 amodb y2 gcd b amodb 根据朴素的欧几里德原理有gcd a b gcd b amodb 则 ax1 by1 bx2 amodb y2 即 ax1 by1 bx2 a a b b y2 ay2 bx2 a b by2 根据恒等定理得 x1 y2 y1 x2 a b y2 这样我们就得到了求解x1 y1的方法 x1 y1的值基于x2 y2 上面的思想是以递归定义的 因为gcd不断的递归求解一定会有个时候b 0 所以递归可以结束 PROBLEM1POJ1006 BiorhythmsTimeLimit 1000MSMemoryLimit 10000KDescriptionSomepeoplebelievethattherearethreecyclesinaperson slifethatstartthedayheorsheisborn Thesethreecyclesarethephysical emotional andintellectualcycles andtheyhaveperiodsoflengths23 28 and33days respectively Thereisonepeakineachperiodofacycle Atthepeakofacycle apersonperformsathisorherbestinthecorrespondingfield physical emotionalormental Forexample ifitisthementalcurve thoughtprocesseswillbesharperandconcentrationwillbeeasier Sincethethreecycleshavedifferentperiods thepeaksofthethreecyclesgenerallyoccuratdifferenttimes Wewouldliketodeterminewhenatriplepeakoccurs thepeaksofallthreecyclesoccurinthesameday foranyperson Foreachcycle youwillbegiventhenumberofdaysfromthebeginningofthecurrentyearatwhichoneofitspeaks notnecessarilythefirst occurs Youwillalsobegivenadateexpressedasthenumberofdaysfromthebeginningofthecurrentyear Youtaskistodeterminethenumberofdaysfromthegivendatetothenexttriplepeak Thegivendateisnotcounted Forexample ifthegivendateis10andthenexttriplepeakoccursonday12 theansweris2 not3 Ifatriplepeakoccursonthegivendate youshouldgivethenumberofdaystothenextoccurrenceofatriplepeak Input Youwillbegivenanumberofcases Theinputforeachcaseconsistsofonelineoffourintegersp e i andd Thevaluesp e andiarethenumberofdaysfromthebeginningofthecurrentyearatwhichthephysical emotional andintellectualcyclespeak respectively Thevaluedisthegivendateandmaybesmallerthananyofp e ori Allvaluesarenon negativeandatmost365 andyoumayassumethatatriplepeakwilloccurwithin21252daysofthegivendate Theendofinputisindicatedbyalineinwhichp e i d 1 Output Foreachtestcase printthecasenumberfollowedbyamessageindicatingthenumberofdaystothenexttriplepeak intheform Case1 thenexttriplepeakoccursin1234days Usethepluralform days eveniftheansweris1 SampleIntput00000001005203432545672831022332020330120340 1 1 1 1SampleOutputCase1 thenexttriplepeakoccursin21252days Case2 thenexttriplepeakoccursin21152days Case3 thenexttriplepeakoccursin19575days Case4 thenexttriplepeakoccursin16994days Case5 thenexttriplepeakoccursin8910days Case6 thenexttriplepeakoccursin10789days SampleInput Output 中国剩余定理 孙子定理 三数为abc余数分别为m1m2m3 为求余计算 证明 令T1 k1 m1 T2 k2 m2 T3 k3 m3 因为k1 a 1 所以T1 a m1 对于a 已知 T2 a 0 T3 a 0 T1 a m1 所以 Answ