# 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 时候 无解。 然后就容易了。求一下欧拉函数，枚举约数即可。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://windmising.gitbook.io/introduction-to-algorithms/acm-jie-ti-bao-gao/3307.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.