3307 A^B = C mod D，已知A，C，D，求解B

ai = x ai-1 + y 递推容易得到 x^n -1 = m a0/t a0' = a0 / gcd(a0,t) 即 ： x^n = 1 mod (a0') 在gcd (x,a0') != 1 时候无解 化简下来就是一个A^B = C mod D的形式，已知A，C，D，求解B。 其实很显然这是一个离散对数问题，这题比较特殊的是化简之后C = 1，也很容易的想到欧拉定理a ^ f(n) = 1 mod n， 题解就是枚举f(n)的各个因子，求出最小的 证明： x = g x' a0' = g a0'' g^n x^n = a0''gm + 1 g ( g^(n-1) x^n -m*a0'' ) = 1 在g > 1 时候 无解。 然后就容易了。求一下欧拉函数，枚举约数即可。