思路:
首先, 由题意, $[x,b_0] = b1 \Rightarrow b_0|b_1$.
设$k_b = \frac{b_1}{b_0}$, 令$b_0 = tg$, 则$b_1 = k_btg$, 当$(k_b,t)=1$时, $(x,b_0) = g$, $x = k_bg$.
同时, $(x,a_0) = a_1 \Rightarrow a_1|x$.
令$x = k_aa_1$, $a_0 = sa_1$, 则有$(s,k_a) = 1$.
由上述一系列结论可以得到该题的算法: 枚举$b_0$的所有因子作为$g$, 判定$(k_b,t)=1$,是否成立, 然后求出$x$, 判定$a_1|x$与$(s,k_a)=1$是否成立即可.
时间复杂度为$O(n * \sqrt{b_0}log\ b_0)$
代码:
1 |
|