题目链接：https://ac.nowcoder.com/acm/problem/212236

到主站看：https://blog.csdn.net/weixin_43346722/article/details/109227175

题目

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

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

输入

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

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

输出

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

样例输入

2
5 7

样例输出

2

样例解释

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

数据范围

对于 的数据，满足
对于 的数据，满足
对于另外 的数据，满足
对于 的数据，满足

思路

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

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

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

比赛时

气死。。。

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

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

代码

#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;
}