結果

問題 No.811 約数の個数の最大化
ユーザー Tiramister
提出日時 2019-04-12 23:10:11
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 1,900 bytes
コンパイル時間 955 ms
コンパイル使用メモリ 82,032 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-15 06:12:56
合計ジャッジ時間 1,623 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

template <class T>
T gcd(T a, T b) {
    while (b > 0) {
        a %= b;
        std::swap(a, b);
    }
    return a;
}

class Prime {
    using lint = long long;

public:
    int MAX_V;
    std::vector<int> primes;
    std::vector<bool> isp;

    explicit Prime(int N) : MAX_V(N) {
        isp.assign(MAX_V + 1, true);
        isp[0] = isp[1] = false;
        for (int i = 2; i * i <= MAX_V; ++i) {
            if (isp[i]) {
                for (int j = i; i * j <= MAX_V; ++j) {
                    isp[i * j] = false;
                }
            }
        }
        for (int p = 2; p <= MAX_V; ++p) {
            if (isp[p]) primes.push_back(p);
        }
    }

    bool isprime(lint N) const {
        if (N <= MAX_V) return isp[N];
        for (lint p : primes) {
            if (p * p > N) break;
            if (N % p == 0) return false;
        }
        return true;
    }

    std::vector<std::pair<lint, int>> factorization(lint N) const {
        std::vector<std::pair<lint, int>> ret;
        for (lint p : primes) {
            if (p * p > N) break;
            if (N % p != 0) continue;
            int cnt = 0;
            while (N % p == 0) {
                N /= p;
                ++cnt;
            }
            ret.emplace_back(p, cnt);
        }
        if (N > 1) ret.emplace_back(N, 1);
        return ret;
    }
};

const Prime P(100010);

int main() {
    int N, K;
    std::cin >> N >> K;

    int ans = 0, maxf = 0;
    for (int n = 1; n < N; ++n) {
        auto facts = P.factorization(gcd(N, n));
        int f = 0;
        for (auto p : facts) f += p.second;
        if (f < K) continue;

        facts = P.factorization(n);
        f = 1;
        for (auto p : facts) f *= (p.second + 1);

        if (maxf < f) {
            ans = n;
            maxf = f;
        }
    }

    std::cout << ans << std::endl;
    return 0;
}
0