結果

問題 No.2075 GCD Subsequence
ユーザー cureskolcureskol
提出日時 2024-11-07 10:44:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,502 ms / 4,000 ms
コード長 2,710 bytes
コンパイル時間 3,139 ms
コンパイル使用メモリ 255,724 KB
実行使用メモリ 11,776 KB
最終ジャッジ日時 2024-11-07 10:44:43
合計ジャッジ時間 23,335 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 28
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/modint>
#include <bits/stdc++.h>
using mint = atcoder::modint998244353;

#include <bits/stdc++.h>

class Prime {
    static inline std::vector<int> primes_, minimum_prime_factor;
    static inline bool is_prepared = false;

  public:
    static void build(int N) {
        assert(!is_prepared);
        is_prepared = true;
        minimum_prime_factor.resize(N + 1);
        std::iota(minimum_prime_factor.begin(), minimum_prime_factor.end(), 0);
        for (int p : std::views::iota(2, N + 1)) {
            if (minimum_prime_factor[p] != p)
                continue;
            primes_.push_back(p);
            if (N / p < p)
                continue;
            for (int q = p * p; q <= N; q += p)
                if (minimum_prime_factor[q] == q)
                    minimum_prime_factor[q] = p;
        }
    }

    static const std::vector<int> &primes() {
        assert(is_prepared);
        return primes_;
    }

    static std::vector<std::pair<int, int>> prime_factors(int n) {
        assert(is_prepared);
        assert(n < minimum_prime_factor.size());
        std::vector<std::pair<int, int>> res;
        while (n != 1) {
            int p = minimum_prime_factor[n];
            if (res.size() and res.back().first == p)
                res.back().second++;
            else
                res.emplace_back(p, 1);
            n /= p;
        }
        return res;
    }

    static std::vector<int> divisors(int n) {
        assert(is_prepared);
        assert(n < minimum_prime_factor.size());
        if (n == 1)
            return {1};
        int p = minimum_prime_factor[n];
        int cnt = 0;
        while (minimum_prime_factor[n] == p)
            n /= p, cnt++;

        auto res = divisors(n);
        int s = res.size();
        res.reserve(s * (cnt + 1));
        for (int i : std::views::iota(0, s)) {
            int d = res[i];
            for (int _ : std::views::iota(1, cnt + 1))
                res.push_back(d *= p);
        }
        return res;
    }
};

constexpr int MAX = 1000000;

int main() {
    int n;
    std::cin >> n;

    std::vector<mint> dp(MAX + 1, 0);
    Prime::build(MAX);

    while (n--) {
        int a;
        std::cin >> a;
        for (const auto &[p, e] : Prime::prime_factors(a))
            for (int _ : std::views::iota(0, e - 1))
                a /= p;

        mint sum = mint::raw(1);
        for (int d : Prime::divisors(a))
            if (d != 1)
                if (Prime::prime_factors(d).size() & 1)
                    sum += dp[d];
                else
                    sum -= dp[d];

        for (int d : Prime::divisors(a))
            dp[d] += sum;
    }

    std::cout << dp[1].val() << std::endl;
}
0