变换
时间限制: 2 Sec 内存限制: 128 MB
题目描述
给出一个序列A，其中第i个数字为ai，你每次可以选择一个数字不变，将其他数字全部乘以x。其中x为任意素数。
无需考虑这些数字在变换过程中是否超过long long的存储范围。请回答：最少经过多少次操作，可以使得序列中所有数字全部相同。
输入
第一行包含一个正整数n，代表序列长度。
接下来一行包含n个正整数，描述序列中的每一个元素。
输出
输出一行一个正整数表示答案。
样例输入 Copy
2 5 7
样例输出 Copy
2
提示
样例说明：
可以选中第二个数字不变，将第一个数字除以5，然后选中第一个数字不变，将第二个数字除以7。两次操作后，数组中所有数字均变为1。当然还有其他方法，如将两个数字最终都变为35也只需要2次操作。
【数据范围】
对于20%的数据，满足n=2,ai≤106
对于40%的数据，满足n≤10,ai≤106
对于另外20%的数据，满足n≤4∗104,ai≤20
对于100%的数据，满足1≤n≤106,1≤ai≤106
固定当前数字，将其他的数字 * prime，等同于将当前选中的数字 / prime
将所有的数字处理到所有的数字都相等，并且还有保证次数最低，那么就要将每个数处理成所有数的gcd大小
首先，先将素数进行筛选，然后将这n个数的gcd(假设为x)求出来，然后再将每一个数字/ x
得到的数字就是要处理的值
将这些值进行分解，看能分解为多少个素数的乘积，过程中需要将结果记录
int n,cnt; int a[maxn],prime[maxn]; bool vis[maxn]; void getPrime(int N) { for(int i=2; i<=N; i++) { if(!vis[i]) prime[++cnt] = i; for(int j = 1; j<cnt&&i*prime[j] <= N; j++) { vis[i * prime[j]] = true; } } } int main() { getPrime(1007); cin >> n; for(int i=1; i<=n; i++) a[i] = read; int gd = a[1]; for(int i=2; i<=n; i++) gd = gcd(gd,a[i]); for(int i=1; i<=n; i++) a[i] /= gd; int ans = 0; for(int i=1; i<=n; i++) { for(int j=1; j<=cnt && prime[j] * prime[j] <= a[i]; j++) { while(a[i] % prime[j] == 0) { ans ++; a[i] /= prime[j]; } } if(a[i] != 1) ans ++; } cout << ans <<endl; return 0; }
