变换 ⁡ \operatorname{变换} 变换

题目链接： nowcoder 212236 ⁡ \operatorname{nowcoder\ 212236} nowcoder 212236

到牛客看：

——>点我跳转<——

题目

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

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

输入

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

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

输出

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

样例输入

2
5 7

样例输出

样例解释

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

数据范围

对于 20 % 20\% 20% 的数据，满足 n = = 2 , a i ≤ 1 0 6 n == 2, a_i \leq 10^6 n==2,ai≤106
对于 40 % 40\% 40% 的数据，满足 n ≤ 10 , a i ≤ 1 0 6 n \leq 10, a_i \leq 10^6 n≤10,ai≤106
对于另外 20 % 20\% 20% 的数据，满足 n ≤ 4 ∗ 1 0 4 , a i ≤ 20 n \leq 4*10^4, a_i \leq 20 n≤4∗104,ai≤20
对于 100 % 100\% 100% 的数据，满足 1 ≤ n ≤ 1 0 6 , 1 ≤ a i ≤ 1 0 6 1 \leq n \leq 10^6, 1 \leq a_i \leq 10^6 1≤n≤106,1≤ai≤106

思路

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

我们可以发现，它选一个数把它以外的其它数都乘一个质数 x x x，其实就相当于把这个数除以 x 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

变换