【CF360D】Levko and Sets 题解

题目大意

  有 $n$ 个数 $a_1...a_n$ 和 $m$ 个数 $b_1...b_m$ 和一个质数 $p$。
  第 $i$ 个集合是这样生成的：一开始只有一个 $1$。每次找集合内的一个元素 $c$ 和一个下标 $j~(j \in [1,m])$，若 $c×a_i^{b_j} \bmod p$ 不在集合里，则加进去。
  求这 $n$ 个集合的并集大小。
  $n\le10^4,\ m\le10^5,\ a_i<p\le10^9,\ b_i<10^9$
  时限 3s。

题解

  极好的数论题。

  第 $i$ 个集合实际上是 $a_i^{\sum 任意b}$。（$任意b$ 是指 $\sum k_jb_j，~k_j \in \mathbb Z$）
  由扩展欧拉定理，指数是模 $p-1$ 意义下的。设 $B=gcd(b_1,b_2,...,b_m,p-1)$，则 $\sum 任意b$ 等价于 $kB$ ($k \in \mathbb Z$)。（你可以用 polya 那套理论来理解这个道理，当只有一个 $b$ 的时候可证它是 gcd，当有多个 $b$ 的时候，合并两个 $b$ 可以看作是其中一个模另一个，因此也是 gcd。）

  底数不同于是用原根来表示，设 $a_i=g^{A_i}$，则第 $i$ 个集合表示为 $g^{A_i kB}$。
  由于 $B$ 是定值，$A_i$ 可以直接视为 $A_i×B$，也相当于一开始把 $a_i$ 视为 $a_i^B$。那么现在第 $i$ 个集合就相当于 $g^{kA_i}$。
  同理，设 $A'_i=\gcd(A_i,p-1)$，则第 $i$ 个集合相当于 $g^{kA'_i}$。

  现在就相当于有一堆 $A'_i$，它们都是 $p-1$ 的约数。求模 $p-1$ 意义下有多少数是某个 $A'_i$ 的倍数。
  这就可以容斥 dp 了。把 $A'_i$ 去重并从大到小排序，然后一个个计算贡献。这里用 $O(n^2)$ 的算法就可以了。

  求 $A'_i$ 有很多种方法。传统方法是先求出原根 $g$，然后求 $A_i$，再求 $A'_i$。当然也有很方便的方法：第 $i$ 个集合的大小也是 $p-1$ 的约数，设为 $d_i=\frac{p-1}{A'_i}$。由于 $A'_i$ 是最大公约数，所以要最小化 $d_i$，即找到最小的 $d_i$ 使得 $a_i^{d_i}≡1$（这里的 $a_i$ 是指 $a_i^B$）。