きたまさ法
きたまさ法は、線形漸化式によって定義された数列の第N項を高速で求めるアルゴリズムである。
A = P_a / Q B = P_b / Q
b_n = a_{n+N} A = R + x^N B P_a / Q = R + x^N P_b / Q P_a = QR + x^N P_b
より、P_aをQで割ったあまりはP_b
P_a = x^N P_b mod Q P_b = x^{-N}P_a mod Q
x^{-N}を繰り返し冪乗法で求めることによりO(deg(Q)^2log(N))で求めることができる
Qの定数項は1なので、a_N = b_0 = P_bの定数項