版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P4861] 按钮 (aka 模板 - 阶)" categories:
Ada 被关在了一个房间里
房间的铁门上有一个按钮, 还有一个显示屏显示着"1"
旁边还有一行小字: "这是一个高精度 M 进制计算器, 每按一次按钮, 屏幕上的数便会乘以 K. 当个位数再次变为 1 时, 门就开了. "
由于 Ada 急于出去, 所以你要在 1s 之内求出她的最小按键次数
一行, 两个整数 M 和 K
一行一个数字, 表示最小按键次数. 如果无论 Ada 按多少次都无法让门打开, 输出"Let's go Blue Jays!" (不含引号)
11 2
10
6 26
Let's go Blue Jays!
对于 30%的数据, $2\leq M,K\leq10^4$
对于 100%的数据, $2\leq M,K\leq2\times 10^{9}$
update: 我们不认为个位为 11,21,...为问题的解 (例如, 11 在 16 进制下记为 B)
即求 $\operatorname{ord}_m(k)$, 可以用扩展 BSGS 或暴力, 此处选用暴力做法
$$ \begin{aligned} \Theta\Bigg(\sqrt{K}+\sum_{d\mid\varphi(K);~d\leqslant\sqrt{\varphi(K)}}\log\varphi(K)\Bigg)&=O\left(\sqrt{K}+\frac{\varphi(K)-\varphi(\varphi(K))}{2}\log\varphi(K)\right)\ &=O\left(\sqrt{K}+\sqrt{\varphi(K)}\log\varphi(K)\right) \end{aligned} $$