ABC293F

jijidawang · 2023-04-26 14:40:12 · 题解

考虑 n 在 b 进制下的最后一位，则可以知道 b 一定是 n 或 n-1 的因子。

使用 Pollard-Rho 算法分解 n 和 n-1 后暴力判断即可。

时间复杂度单次 O(n^{1/4}+d(n)\log n)，不过数据不是很满所以可以过。