$$\mathrm{变换}$$

题目链接：$\mathrm{n}\mathrm{o}\mathrm{w}\mathrm{c}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{r}212236$

关于这场比赛

——>点我可以查看其它题目（目录）<——

到牛客看：

——>点我跳转<——

题目

给出一个序列 $A$，其中第 $i$ 个数字为 $a_i$，你每次操作可以选择一个数字不变，其他数字乘以 $x$，其中 $x$ 为任意素数

无需考虑这些数字在变换过程中是否超过 long long 的存储范围。请回答：最少经过多少次操作，可以使得序列中所有数字全部相同。

输入

第一行包含一个正整数 $n$，代表序列长度。

接下来一行包含 $n$ 个正整数，描述序列中的每一个元素。

输出

输出一行一个正整数表示答案。

样例输入

2 5 7

样例输出

2

样例解释

可以选中第二个数字不变，将第一个数字除以 $5$，然后选中第一个数字不变，将第二个数字除以 $7$。两次操作后，数组中所有数字均变为 $1$。当然还有其他方法，如将两个数字最终都变为 $35$ 也只需要 $2$ 次操作。

数据范围

对于 $20\%$ 的数据，满足 $n==2,a_i\le 10^6$ 对于 $40\%$ 的数据，满足 $n\le 10,a_i\le 10^6$ 对于另外 $20\%$ 的数据，满足 $n\le 4\ast 10^4,a_i\le 20$ 对于 $100\%$ 的数据，满足 $1\le n\le 10^6,1\le a_i\le 10^6$

思路

这道题是一道涉及了质因数和最大公因数的题目。

我们可以发现，它选一个数把它以外的其它数都乘一个质数 $x$，其实就相当于把这个数除以 $x$。 （因为我们最后要让所有数一样，所以是可以的）

那我们要让所有数一样，就可以先找到所有数的最大公因数，然后把所有数除到这个最大公约数就可以了。 那其实就是把所有数除以最大公约数，然后分解质因子，统计一共分解出了多少个数，就是答案。

比赛时

气死。。。

当天题目一开始是有两种操作：一种是选一个其它乘数，一种是选一个其它除以数。 我想到思路，但是就是因为有除以数的操作，就做不了。

比完赛才知道题目改了，第二个操作没了。 生草。。。

代码

#include<cmath> #include<cstdio> using namespace std; int n, a[1000001], allgcd, ans, su[1000001], sky; bool susu[1000001]; int gcd(int x, int y) { if (!y) return x; return gcd(y, x % y); } int main() { for (int i = 2; i <= 1000000; i++) if (!susu[i]) { su[++su[0]] = i; for (int j = i + i; j <= 1000000; j += i) susu[j] = 1; } scanf("%d", &n); scanf("%d", &a[1]); allgcd = a[1]; for (int i = 2; i <= n; i++) { scanf("%d", &a[i]); allgcd = gcd(allgcd, a[i]); } for (int i = 1; i <= n; i++) a[i] /= allgcd;//所有数除以所有数的gcd for (int i = 1; i <= n; i++) { sky = floor(sqrt(a[i])); for (int j = 1; j <= su[0] && su[j] <= sky; j++) while (a[i] % su[j] == 0) { ans++;//分解质因子，记录全部的个数 a[i] /= su[j]; } if (a[i] > 1) ans++;//可能剩下一个质数 } printf("%d", ans); return 0; }