mayoko’s diary

プロコンとかいろいろ。

SRM 534 div1 med: EllysNumbers

解法

互いに素なものしか使えませんが, 例えば n が 4 の倍数の時, 掛け算の要素として 2 を選んでしまうと, もうひとつ 2 の倍数を取らないといけなくなるので, 条件に合いません。

このように, n の各素因数に対して, 一つの数だけでその素因数の指数分だけ指数が揃ってないとダメです。
それに気づけば, 後は簡単な bitDP で解けます。10^18 まででは, 素因数の数はたかだか 18 個程度(2*3*...*43 とすると 10^18 は超えている) なので, dp[n][state] = (n 番目の時点で, n の素因数のうち state で表されるものだけはすでに掛け算されている場合の, 残りの数の選び方) とすれば良いです。

map<int, int> bun(int x) {
    map<int, int> M;
    for (int i = 2; i*i <= x; i++) {
        int cnt = 0;
        while (x%i == 0) {
            x /= i;
            cnt++;
        }
        if (cnt) M[i] += cnt;
    }
    if (x > 1) M[x] += 1;
    return M;
}

class EllysNumbers {
public:
    long long getSubsets(long long n, vector <string> special) {
        string s;
        for (string t : special) s += t;
        stringstream ss(s);
        vector<vi> vs;
        map<int, int> mp;
        while (ss >> s) {
            int tmp = stoi(s);
            if (n%tmp) continue;
            map<int, int> M = bun(tmp);
            ll r = n/tmp;
            bool ng = false;
            vector<int> v;
            for (auto p : M) {
                if (__gcd(r, (ll)p.first) > 1) ng = true;
                v.push_back(p.first);
                mp[p.first] = 0;
            }
            if (ng) continue;
            vs.push_back(v);
        }
        {
            ll tmp = n;
            for (auto p : mp) {
                while (tmp%p.first == 0) tmp /= p.first;
            }
            if (tmp > 1) return 0;
        }
        int size = 0, vsize = vs.size();
        for (auto& p : mp) p.second = size++;
        vector<int> flags(vsize);
        for (int i = 0; i < vsize; i++) {
            int flag = 0;
            for (int el : vs[i]) flag |= 1<<mp[el];
            flags[i] = flag;
        }
        vector<ll> dp(1<<size);
        dp[0] = 1;
        for (int i = 0; i < vsize; i++) {
            vector<ll> _dp(1<<size);
            for (int j = 0; j < 1<<size; j++) {
                _dp[j] += dp[j];
                if (j&flags[i]) continue;
                _dp[j|flags[i]] += dp[j];
            }
            dp = _dp;
        }
        return dp[(1<<size)-1];
    }
};