题意分析

我们需要找出轮流行动的两人谁将胜出，两人都有同样的武器，首先将星球尺寸缩小到1的一方获胜

解题思路

我们需要找出一种必胜策略，从而判断两人谁先获胜，用dfs递归来实现，遍历所有武器，如果有武器能直接使星球小于1，那么直接获胜，或者如果有武器能使对方一定不获胜，那么获胜，或者所有武器均使对手必胜，那么失败。

标程

#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <functional>

using namespace std;

typedef long long ll;

const ll BASE = 1000000;

int main() {
    int N;
    cin >> N;

    while (N--) {
        double X;
        int K;
        cin >> X >> K;
        vector<double> factors(K);
        for (int i = 0; i < K; i++) {
            cin >> factors[i];
        }

        ll X_int = ll(round(X * BASE));
        vector<ll> factor_ints;
        for (int i = 0; i < K; i++) {
            factor_ints.push_back(ll(round(factors[i] * BASE)));
        }

        map<ll, bool> dp;

        function<bool(ll)> dfs;
        dfs = [&](ll s) -> bool {
            if (s <= BASE) {
                return false;
            }
            if (dp.find(s) != dp.end()) {
                return dp[s];
            }
            for (ll f_int : factor_ints) {
                ll ns = (s * f_int) / BASE;
                if (ns <= BASE) {
                    return dp[s] = true;
                }
            }
            for (ll f_int : factor_ints) {
                ll ns = (s * f_int) / BASE;
                if (!dfs(ns)) {
                    return dp[s] = true;
                }
            }
            return dp[s] = false;
        };

        bool result = dfs(X_int);
        if (result) {
            cout << "Nils" << endl;
        } else {
            cout << "Mikael" << endl;
        }
    }

    return 0;
}