SRM657 div2 1000

問題

整数a,b,cが与えられたとき、(a*x^2+b*x+c) mod 10^9 = 0となる整数xを返す。
ただし、0<=x<10^9に複数解があれば、どれか一つ、解がなければ-1を返す。

0<=a,b,c<10^9

考え方

法Mが合成数の場合、「f(x)=n mod M」は、Mを素因数分解した場合「f(x)=n mod p^a」「f(x)=n mod q^b」(M=(p^a)*(q^b)*..., p,qは素数)が成り立つ(中国剰余定理)。
なので、今回は10^9=(2^9)*(5^9)から、①「f(x)=0 mod 2^9」と②「f(x)=0 mod 5^9」であるようなxを求める問題に帰着できる。

この2つのf(x)=0となるxを求めるのは、2^9=512、5^9=1,953,125なので、全探索すれば求められる。(どちらかの解がなければ-1)
なので、それぞれ求めたx1(mod2^9での解の一つ),x2(mod5^9での解の一つ)について、①は「x=x1 mod 2^9」、②は「x=x2 mod 5^9」と考えられる。
この連立線形合同式を解くのは、蟻本にあるようにGCDを使って求める方法や、②を変形した「x=x2+5^9*t」を①に代入した「x2+5^9*t=x1 mod 2^9」をx2+5^9*tが10^9未満で探索してもよい。