题解 | #变换# #质因数分解# #数论#

牛客7606D - 变换

• https://ac.nowcoder.com/acm/contest/7606/D

题意

• 给出一个长度为 $n(n\le 10^6)n(n\backslash leq\; 10^6)$ 的序列 $a_i(1\le a_i\le 10^6)a\_i(1\backslash leq\; a\_i\backslash leq\; 10^6)$，你每次操作可以选择一个数字不变，其他数字乘以任意一个质数
• 求出：为使序列中所有数字两两相同，至少需要的操作次数

思路

• 最终序列中所有数字两两相同，那么这个数字是什么？
  • 假设这个数字是 $AA$，那么 $AA$ 可以写成 $p_1^{x_1}\times p_2^{x_2}\times \cdots \times p_k^{x_k}p\_1^\{x\_1\}\backslash times\; p\_2^\{x\_2\}\backslash times\; \backslash dots\; \backslash times\; p\_k^\{x\_k\}$ 的形式，设 $P_1=\{p_1,p_2,\dots p_k\}P\_1=\backslash lbrace\; p\_1,p\_2,\backslash dots\; p\_k\backslash rbrace$
  • 对于$i\in [1,n]i\; \backslash in\; [1,n]$，将每个 $a_{i}a\_i$ 质因数分解，将质因数放入集合 $P_{2}P\_2$ 中（一边放入一边去重，$P_{2}P\_2$ 中无重复元素）
  • 那么，$P_1=P_{2}P\_1\; =\; P\_2$，也就是说，数字 $AA$ 的每个质因子，都能由至少一个 $a_{i}a\_i$ 经分解质因子得到
• 操作 “选择一个数字不变，其他数字乘以任意一个质数”，相当于
• 对于每个集合 $P_{2}P\_2$ 中的质因子 $pp$，用 $f(x)f(x)$ 表示：满足 $pp$ 出现了至少 $xx$ 次的 $a_{i}a\_i$ 的数量，形式化地，$f(x)={\sum }_{i=1}^n[a_i\mathrm{\mid }{p}^x]f(x)=\backslash sum\_\{i=1\}^\{n\}[a\_i\; |\; p^x]$，此时 $f(x)f(x)$ 对答案的贡献是 $f(x)\mathrm{m}\mathrm{o}\mathrm{d}nf(x)\backslash mod\; n$