由于首位不能是 \(0\) ，因此首位有 \(b-1\) 种可能性。其他 \(n-1\) 位有 \(b^{n-1}\) 种可能。因此这些数总计
\((b-1) b^{n-1}\)
每页 \(c\) 个数，求最后一页有多少个数，即求
\(\text { ans }=(b-1) b^{n-1} \quad \bmod c\)
注意到题目中 \(b, n\) 都非常大，采用扩展欧拉定理进行降幂处理：
\(\begin{aligned} \text { ans } & =(b-1) b^{n-1} \bmod c \\ & =((b-1) \bmod c)(b \bmod c)^{n-1} \bmod c \\ & =\left\{\begin{array}{lll} ((b-1) \bmod c)(b \bmod c)^{(n-1)\bmod \varphi(c)} \bmod c & \operatorname{gcd}(b, c)=1 \\ ((b-1) \bmod c)(b \bmod c)^{n-1} \bmod c & \operatorname{gcd}(b, c) \neq 1, n-1<\varphi(c) \\ ((b-1) \bmod c)(b \bmod c)^{(n-1) \bmod \varphi(c)+\varphi(c)} \bmod c & \operatorname{gcd}(b, c)=1, n-1 \geq \varphi(c) \end{array}\right. \end{aligned}\)
扩展欧拉定理的证明可参考 OI wiki
最后若 \(ans = 0\)，则输出 \(c\)，否则输出 \(ans\)。
标签：gcd,CF17D,题解,bmod,Notepad,ans From： https://www.cnblogs.com/jxy2012/p/18149188