11272: 【原1272】写数游戏

题目

题目描述

author: Chen Xutong 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1272

Description

纸上已经有n个数，每次随便取两个，用大的除一下得到结果，如果发现纸上没有，就写到纸上去，直到写不出为止。问纸上最后有几个数？

Sample Input1

2
9 2

Sample Output1

3

开始有 9 和 2，他可以再加上4，因为 9 div 2 = 4。 在他写完4之后就没什么可写的了，因为9 div 4 = 2，和 4 div 2 = 2。纸上就有 9，2 和 4。

Sample Input2

6
1 5 8 30 15 4

Sample Output2

11

数据范围

n <= 100

每个数 x_i <= 100

ligongzzz's solution

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<int> vdata(n);
    unordered_map<int, bool> mdata;

    for (int i = 0; i < n; ++i) {
        cin >> vdata[i];
        mdata.insert(make_pair(vdata[i], true));
    }

    for (int i = 0; i < vdata.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            int ans = vdata[i] > vdata[j] ? vdata[i] / vdata[j] : vdata[j] / vdata[i];
            if (mdata.find(ans) == mdata.end()) {
                vdata.emplace_back(ans);
                mdata.insert(make_pair(ans, true));
            }
        }
    }

    cout << vdata.size();

    return 0;
}