[CF772C] Vulnerable Kerbals

令 $a_i=\prod_{j=1}^iA_j$，那么条件转化为

• $a_i\in[0,m)$
• 对于 $i\not=j$ 有 $a_i\not=a_j$
• $a_i\not\in B$
• $\gcd(a_{i-1},m)\mid a_i$

朴素的想法是对 $[0,m)\backslash B$ 中所有满足 $\gcd(x,m)\mid y$ 的 $x$ 向 $y$ 连边，那么图上的最长链长度即为答案。

但是图上有环，难以处理。不过不难发现 $x,y$ 在同一环中当且仅当 $\gcd(x,m)=\gcd(y,m)$。也就是说如果能取 $x$，那么一定能取 $\gcd(y,m)=x$ 的所有 $y\not\in B$。

所以我们将所有 $x$ 按照 $\gcd(x,m)$ 划分等价类建图，在 DAG 上 DP 即可。