$$\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;
}

本文地址：https://blog.csdn.net/weixin_43346722/article/details/109227175