题目描述：

        小红有一个数组，她每次可以选择数组的一个元素 xxx ，将这个元素分成两个元素 aaa 和 bbb ，使得 a+b=xa+b=xa+b=x。请问小红最少需要操作多少次才可以使得数组的所有元素都相等。

输入描述:

        第一行输入一个整数 n(1≤n≤10^5) 表示数组长度。第二行输入 n个整数表示数组 a(1≤ai≤10^9) 。

输出描述:

        输出一个整数表示答案。

示例1

输入：

2
2 4

输出：

1

说明：

操作1次，将4分成2和2，数组变成[2,2,2]。

解题步骤1（错误）：

        由题可知，想要将所有的正整数都转换成一个数，那么找到这些整数的最大公因子即可。

        ①输入

        ②将各个整数所有小于最小正整数的因子所对应的数组进行++：先创建一个数组用于存储该下标i可以是多少个正整数的因子，其中该数组的个数应该为最小整数+1个；再利用双层循环来判断该数组下标i是否可以成为因子，如果可以则其值+1，最终就可以填充b数组b中的值

        ③找到最大共同的因子：即数组b中的数组下标j对应的值为n，这个最大的公共因子就是j

        ④计算次数：每个数进行转换的时候，需要转换  /公共因子-1 次

        ⑤输出

代码：

#include<iostream>
#define MAX 1000000000
using namespace std;
int  main()
{//输入int n;  //整数个数cin >> n;int* a = new int[n];    //存储整数int mi = MAX;    //记录最小的正整数for (int i = 0;i < n;i++){cin >> a[i];mi = min(a[i], mi);}//将各个整数所有小于最小正整数的因子所对应的数组进行++int* b = new int[mi + 1];   //存储因子是多少个正整数的因子for (int i = 0;i < mi + 1;i++)   //初始化b{b[i] = 0;}for (int i = 0;i < n;i++){for (int j = 1;j < mi + 1;j++){if (a[i] % j == 0)  //可以被整除，即j是因子{b[j]++;}}}//找到最大共同的因子（即其数组对应的值为n）int x = 0;   //最终数组变成的元素for (int j = mi;j > -1;j--){if (b[j] == n){x = j;break;}}//计算次数int count = 0;   //操作次数for (int i = 0;i < n;i++){count += a[i] / x - 1;}//输出cout << count << endl;system("pause");return 0;
}

错误原因：

        在步骤②时，如果最小的整数过大，将会导致计算b的次数过大；当整数的个数过大的时候，也将会导致计算b的次数过大，所以最终就会导致运算超时

解题思路2（改进）：

        在计算b的时候，可以利用gcd()函数来计算出最大的公约数，直接过渡到计算操作次数就可以了。

注意：

        ①操作次数可能会很大，必须使用long long的数据类型。

代码 ：

#include<iostream>
using namespace std;//找最大公约数
int gcd(int a, int b)
{while (b != 0){int temp = b;b = a % b;a = temp;}return a;
}int  main()
{//输入int n;  //整数个数cin >> n;int* a = new int[n];    //存储整数cin >> a[0];int g = a[0];   //最大公约数for (int i = 1;i < n;i++){cin >> a[i];g = gcd(g, a[i]);}//计算次数long long count = 0;   //操作次数for (int i = 0;i < n;i++){count += a[i] / g - 1;}//输出cout << count << endl;system("pause");return 0;
}