ZeroJudge B112: 高中運動會

夢幻城市每年爲全市高中生舉辦一次運動大會。為促進各校同學之間的交流，採用特別的分隊方式：每一個學校的同學，必須被均勻分散到各隊，使得每一隊中該校的人數皆相同。爲增加比賽的競爭性，希望分成越多隊越好。你的任務是由各校的人數，決定最多可分成的隊數。

範例測資

範例輸入範例輸出
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
標籤

相關文章

發佈留言