显然要关于 \(k\) 离线。
对于固定的 \(k\)，关于 \(k\) 的质因子的个数讨论：
- 如果 \(k\) 是形如 \(p^\alpha\) 的素数幂
只需判断 \(p|n\) 即可。
- 否则
我们可以跑类似同余最短路。
当 \(\min p_i\) 很大的时候，过不去。
但是，极限数据只能在形如 \(k=p_1^{\alpha_1}p_2^{\alpha_2}\) 才能成立。
这种情况我们可以跑 exgcd。
所以，在 \(k\) 的质因子个数为 \(2\) 时用 exgcd 判断不定方程存在正整数解，\(>2\) 时跑同余最短路。