显然要关于 \(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\) 时跑同余最短路。
\(\color{green}{\checkmark}\)!
标签:报告,短路,exgcd,解题,CF986F,alpha,同余 From: https://www.cnblogs.com/BK0717/p/17724813.html