> For the complete documentation index, see [llms.txt](https://windmising.gitbook.io/introduction-to-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://windmising.gitbook.io/introduction-to-algorithms/acm-jie-ti-bao-gao/3307.md).

# 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''*g*m + 1 g ( g^(n-1)* x^n -m\*a0'' ) = 1 在g > 1 时候 无解。 然后就容易了。求一下欧拉函数，枚举约数即可。