【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);
}

最后

以上就是舒服大碗为你收集整理的【2020.10.20 牛客 普及组 模拟赛2】T4 变换的全部内容，希望文章能够帮你解决【2020.10.20 牛客 普及组 模拟赛2】T4 变换所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。