与上一题类似,我们可以考虑生成函数。但是由于本题是 $\mod m$ 意义下的乘法,所以我们可以把原来的乘法转换为与 $m$ 的原根的对数的加法。再用上题目类似的思路即可。

定义生成函数 $f$ :

$$
f(x) = \sum\limits_{i=0}^{\varphi(m)} tag(i) \times x^i
$$

其中 $tag(i) = 1$ 当且仅当存在 $x \in S$ 使得 $\log_g x = i$ 。

最后答案为:

$$
[x^k]f^n(x)
$$

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×