解法

概要

上手くを使う。

詳細

を展開すると次のようになる:

明らかに分かる必要条件はふたつ:

  • 素数について
  • 素冪について かつ かつ

逆に、これら以外の数についてはとする解法がありそう。 ここまでは自然に分かる。

ここで対数を取る。 としそれ以外は とすると という準同型性からすべて上手くいく。 どうやって思い付くのかは不明。

メモ

ここ最近で一番の天才解法

実装

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define ALL(x) begin(x), end(x)
using ll = long long;
using namespace std;

vector<vector<int> > sieve_prime_factors(int n) {
    vector<vector<int> > ps(n);
    REP3 (a, 2, n) {
        if (ps[a].empty()) {
            for (int b = 2 * a; b < n; b += a) {
                for (int b1 = b; b1 % a == 0; b1 /= a) {
                    ps[b1].push_back(a);
                }
            }
        }
    }
    return ps;
}

vector<ll> solve(int n, int m, vector<int> const & c) {
    auto prime_factors = sieve_prime_factors(n + 1);
    vector<int> is_required(n + 1);
    REP (i, n + 1) {
        if (i == 0 or i == 1) continue;
        auto const & ps = prime_factors[i];
        if (ps.empty()) {
            is_required[i] = i;  // a prime
        } else if (count(ALL(ps), ps.front()) == ps.size()) {
            is_required[i] = ps.front();  // a prime-power
        }
    }
    for (int c_i : c) {
        if (is_required[c_i]) return vector<ll>();
    }

    constexpr ll MULTIPLIER = 1e9;
    vector<ll> a(n + 1);
    REP (i, n + 1) {
        if (is_required[i]) {
            a[i] = log(is_required[i]) * MULTIPLIER;
        }
    }
    return a;
}

int main() {
    int n, m; cin >> n >> m;
    vector<int> c(m);
    REP (i, m) cin >> c[i];
    auto a = solve(n, m, c);
    if (a.empty()) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
        REP3 (i, 1, n + 1) cout << a[i] << ' ';
        cout << endl;
    }
    return 0;
}