Description
ACM-SCPC-2017 is approaching every university is trying to do its best in order to be the Champion, there are n universities, the ith of them has exactly ai contestants. No one knows what is the official number of contestants in each team yet, this year organizers are planing to minimize number of teams participating in the contest but they still want every contestant to participate, so they should select a number k so that each team will consist of exactly k contestant from the same university. Every contestant will belong to one team exactly, and number of these teams is as minimum as possible. Your job is to help the organizers in their task by writing a program that calculates two integers k, the number of contestants in each team, and m, the minimum number of teams will participate. 1 ≤ n ≤ 1000, 1 ≤ ai ≤ 106
Input
First line of input contains an integer T denotes number of test cases. Each test case contains two lines: the first line contains one integern denotes number of universities, while the second line contains n space-separated integers the ith of them denotes number of contestants from the ith university.
Output
For each test case, print one line containing two integers: the first one is k, the size of each team, and the second one is m, the minimum number of teams from all universities according to the previous conditions.
Example input
2
3
5 15 10
4
4 6 8 12 output
5 6
2 15
題意：有n支隊，每個隊都有ai的隊員，現在重新配置設定人數，每個隊人數相同，且隻有相同學校的才能組隊，要求隊伍數量最少
解法：相同學校的才能組隊，也就是說每個隊的人數必須都能整除ai，那麼應該是求ai的gcd，隊伍數量就是拿人數除以gcd #include<bits/stdc++.h>
using namespace std;
int a[100000];
int main()
{
int n,m;
int t;
cin>>t;
while(t--)
{
int num;
int sum=0;
cin>>n;
cin>>a[1];
num=a[1];
sum+=a[1];
for(int i=2;i<=n;i++)
{
//int num;
cin>>a[i];
sum+=a[i];
num=__gcd(a[i],num);
}
cout<<num<<" "<<sum/num<<endl;
}
return 0;
轉載于:https://www.cnblogs.com/yinghualuowu/p/6044085.html