【2020.10.20 牛客 普及组 模拟赛2】T4 变换

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

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

---

输入描述: 第一行包含一个正整数 n，代表序列长度。

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

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

---

示例1 输入 2 5 7 输出 2

---

说明 可以选中第二个数字不变，将第一个数字除以 5，然后选中第一个数字不变，将第二个数字除以 7。两次操作后，数组中所有数字均变为 1。当然还有其他方法，如将两个数字最终都变为 35 也只需要 2 次操作。 备注: 对于 $20$% 的数据，满足 $n==2,a_i\le 10^6$

对于 $40$% 的数据，满足$10^{6}n\le 10,a_i\le 10^6$

对于另外 $20$% 的数据，满足 $n\le 4\ast 10^4,ai\le 20$

对于 $100$% 的数据，满足 $1\le n\le 10^6,1\le a_i\le 10^6$

---

解题思路 对于任何一列数来说，选取一个数，让其它数乘一个素数其实就等价于让选取的数除以一个素数，所以这道题就转换为如下题目：

给定一个序列，其中第 i 个数字为 ai，你每次操作可以选择一个数字除以x，x为任意素数，请问最少经过多少次操作，可以使得序列中所有数字全部相同。

让所有数字相同，即使所有数字的$GCD$，于是它又可以转换为如下题目:

给定一个序列，其中第 i 个数字为 $ai$，你每次操作可以选择一个数字除以x，x为任意素数，请问最少经过多少次操作，才可以让每个数都变成所有原数的$GCD$。

所以就很简单了，分解序列中每个数的质因数，除去$GCD$，相加

---

代码

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<queue> using namespace std; int n,sum,a[1100000],pri[10005],v[10005],ans; int GCD(int a,int b) { if(b==0) return a; return GCD(b,a%b); } void zs(){ for(int i=2;i<=10005;i++) { if(!v[i]) pri[++pri[0]]=i; for(int j=1;j<=pri[0]&&pri[j]*i<=10005;j++) v[j*i]=1; } } int main(){ scanf("%d",&n); zs(); for(int i=1;i<=n;i++) scanf("%d",&a[i]); sum=a[1]; for(int i=2;i<=n;i++) sum=GCD(sum,a[i]); for(int i=1;i<=n;i++) a[i]=a[i]/sum; for(int i=1;i<=n;i++) { for(int j=1;j<=pri[0]&&pri[j]*pri[j]<=a[i];j++) { while(a[i]%pri[j]==0) { a[i]/=pri[j]; ans++; } if(a[i]==1) break; } if(a[i]!=1) ans++; } printf("%d",ans); }