square869120Contest #2 B - Division 2

面白かったです。

問題

s8pc-2.contest.atcoder.jp

解法

「どの数で割られるか」で 2^q の場合分けをします。

i1, i2, ..., im 番目の数で割られて 1 になる場合, 元の数は q[i1] * a[i2] * ... * a[im] です。
これが本当に i1, i2, ..., im でのみ割られるかをチェックしなければなりませんが, それはシミュレーションするだけで確かめられます。

int a[30];
int q;

ll calc(ll n, int s) {
    ll mul = 1;
    for (int i = 0; i < q; i++) if ((s>>i)&1) {
        mul *= a[i];
        if (mul > n) mul = n+1;
    }
    if (mul > n) return mul;
    ll ret = mul;
    for (int i = 0; i < q; i++) {
        if ((s>>i)&1) mul /= a[i];
        else if (mul%a[i]==0) return n+1;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n >> q;
    for (int i = 0; i < q; i++) {
        cin >> a[i];
    }
    set<ll> S;
    for (int s = 0; s < 1<<q; s++) {
        S.insert(calc(n, s));
    }
    int ans = 0;
    for (ll el : S) if (el <= n) ans++;
    cout << ans << endl;
    return 0;
}