>Link
>Description 给出一个序列A，其中第 i 个数字为 a i a_i ai ，你每次可以进行一种操作: 选择一个数字不变，将其他数字全部乘以 x。其中 x 为任意素数。
请问：最少经过多少次操作，可以使得序列中所有数字全部相同。
>解题思路 考试的时候看到这道题，准备做20分但是不知道为什么挂了==。正解就跟我的20分思想差不多。
玩一下这个游戏就可以发现，最终我们会把这n个数都变成它们的gcd。 所以我们把每个数达到gcd要除以的所有的质因子总数加起来就行了
因为游戏规则是选择一个数不变，把其他所有的数乘一个素数，这就相当于把这一个数除以一个素数
>代码
#include <iostream> #include <cstdio> #include <cstring> #define N 1000005 using namespace std; int n, a[N], g, ans; int gcd (int a, int b) { if (!b) return a; return gcd (b, a % b); } int main() { scanf ("%d", &n); for (int i = 1; i <= n; i++) scanf ("%d", &a[i]); g = a[1]; for (int i = 2; i <= n; i++) g = gcd (g, a[i]); for (int i = 1; i <= n; i++) { a[i] /= g; for (int j = 2; j * j <= a[i]; j++) while (a[i] % j == 0) { a[i] /= j; ans++; } ans += a[i] > 1 ? 1 : 0; } printf ("%d", ans); return 0; }