传智杯 第六届-复赛-C
题目描述：
小红有一个数组，她每次可以选择数组的一个元素 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;
}