Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

POJ 1006 Biorhythms ( CRT, ExtGCD )

1006 -- Biorhythms題意: 細節不好說明,但總之給 p, i, e, d,滿足聯立模方程式: ( x + d ) % 23 = p ( x + d ) % 28 = e ( x + d ) % 33 = i 求 x。解法: 就是一個中國剩餘定理模板。28 非質數,如果要用尤拉定理搞要先求 phi 函數才能求模逆元,但最近…

CFR 7 C. Line ( Extgcd, Math )

http://codeforces.com/contest/7/problem/C題意: 給一個方程式 Ax + By + C = 0,找一組整數 ( x, y ) 在該直線上。或者判斷不存在。解法: 先用 ext_gcd 判斷 Ax + By = gcd( A, B ) 時的 x, y 分別是多少。 ext_gcd 要背!不懂還是要硬背!( 我總是想不…