square869120Contest #2 D - 2016

問題

s8pc-2.contest.atcoder.jp

解法

「約数 多い」で調べると, 高度合成数という言葉が出てきます。
高度合成数 - Wikipedia

結局この問題ではこれを求めろ, ということなのですが, 高度合成数には次のような特徴があるようです。

高度合成数は

という形で素因数分解され、

また, 2, 36 以外では [a_p = 1] が成り立つようですが今回はそれは使いませんでした。

これを利用して, 高度合成数としてあり得るものを dfs して列挙しましょう。これはゆーて探索範囲がそれほど多くならないので十分時間内に間に合います。

下の探索手法では 25000 個程度の候補で間に合ったので, 各クエリごとに n 以下の数を全部調べて約数最大のものを調べれば OK です。

const ll MAX = 1e17;
vector<ll> S;
ll prime[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};

void dfs(int i, int num, ll now) {
    S.push_back(now);
    for (int j = 1; j <= num; j++) {
        now *= prime[i];
        if (now > MAX) break;
        dfs(i+1, j, now);
    }
}

ll calc(ll x) {
    ll ret = 1;
    for (int i = 0; i < 17; i++) {
        ll tmp = 0;
        while (x%prime[i] == 0) {
            x /= prime[i];
            tmp++;
        }
        ret *= tmp+1;
    }
    return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    dfs(0, 60, 1);
    sort(S.begin(), S.end());
    S.erase(unique(S.begin(), S.end()), S.end());
    vector<ll> cnt(S.size());
    for (int i = 0; i < S.size(); i++) {
        cnt[i] = calc(S[i]);
//        cout << S[i] << "  " << cnt[i] << endl;
    }
    int Q;
    cin >> Q;
    while (Q--) {
        ll n;
        cin >> n;
        ll c = 0, ans = 0;
        for (int i = 0; i < S.size(); i++) {
            if (S[i] > n) break;
            if (cnt[i] > c) {
                c = cnt[i];
                ans = S[i];
            }
        }
        cout << c << " " << ans << endl;
    }
    return 0;
}