小目录
链接题目描述样例输入样例输出数据范围或提示思路代码
链接
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;
}
