【质因数分解】牛客模拟赛#2 D-变换

小目录

链接

D - 变换

题目描述

样例输入

2
5 7

样例输出

2

数据范围或提示

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

数据范围

思路

其实题目就是每次选一个数，使它除以一个质因子x
那么最后肯定是要变为gcd的
我们就求出gcd后，每个数除以它，然后求质因子根数之和就好了

代码

#include<iostream>
#include<cstdio>

using namespace std;

int n, gcdx, a[1000005], ans;

int gcd(int x, int y)
{
	if (!y) return x;
	return gcd(y, x % y);
}

int main()
{
	scanf("%d", &n);
	scanf("%d", &a[1]);
	gcdx = a[1];
	for (int i = 2; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		gcdx = gcd(a[i], gcdx);	
	}	
	for (int i = 1; i <= n; ++i)
		a[i] /= gcdx;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 2; j * j <= a[i]; ++j)
		{
			while (!(a[i] % j)) {
				a[i] /= j; 
				ans++;
			}
		}
		if (a[i] > 1) ans++;
	}//求质因子
	printf("%d", ans);
	return 0;
}