夢幻城市每年爲全市高中生舉辦一次運動大會。為促進各校同學之間的交流,採用特別的分隊方式:每一個學校的同學,必須被均勻分散到各隊,使得每一隊中該校的人數皆相同。爲增加比賽的競爭性,希望分成越多隊越好。你的任務是由各校的人數,決定最多可分成的隊數。
範例測資
範例輸入 | 範例輸出 |
---|---|
EOF 輸入,輸入檔第一行為一個介於 1 到 500 間的正整數 N,代表學校的個數。皆下來有 N 行,每行為一個介於 1 到 10000 間的正整數,分別代表這 N 個學校的人數。 | 最多可分成的隊數。 |
3 12 16 20 4 400 200 150 625 | 4 25 |
解題思路
收資料的時候先把收到數字的因數存到一個 Map 中,然後建立一個 Vector 的資料結構將每個學校的因數 Map 都存放進去。
之後使用 Auto 跑第一個學校的 Map 的 For迴圈,並且和其他學校的 Map 比較看有沒有出現一樣的因數,如果所有學校都有相同的因數則先將答案設為這個因數,取最大值。
範例程式碼-ZeroJudge B112: 高中運動會
#include <iostream>
#include <vector>
#include <math.h>
#include <map>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
int N;
while (cin >> N)
{
vector<int>num;
vector<map<int, int>>vMAP;
for (int i = 0; i<N; i++)
{
int tmp;
cin >> tmp;
num.push_back(tmp);
map<int, int>MAP;
for (int j = 2; j<int(sqrt(tmp))+1; j++)
{
if (tmp % j == 0)
{
MAP[j]++;
MAP[tmp/j]++;
}
}
vMAP.push_back(MAP);
}
int ans = 1;
for (auto it:vMAP[0])
{
int factor = it.first;
bool ok = true;
for (int i = 1; i<N; i++)
{
if (vMAP[i][factor] == 0)
{
ok = false;
break;
}
}
if (ok) ans = factor;
}
cout << ans << "\n";
}
}
//ZeroJudge B112
//Dr. SeanXD