12169专题

Disgruntled Judge UVA - 12169

Disgruntled Judge UVA - 12169 题意:给定2*T大小的数组,给定奇数项,符合关系x[i] = (a · x[i−1] + b) mod 10001.求各个偶数项。 题解:范围10000,可以通过暴力求解过,但是时间复杂度太高,根据公式可以采用拓展欧几里得求解。    可以得到  x2 = (a * x1 + b) % 10