結果

問題 No.1781 LCM
ユーザー 👑 NachiaNachia
提出日時 2021-12-16 00:32:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4,075 ms / 5,000 ms
コード長 6,520 bytes
コンパイル時間 1,273 ms
コンパイル使用メモリ 89,892 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-11-22 04:27:22
合計ジャッジ時間 28,227 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 4 ms
5,248 KB
testcase_03 AC 4 ms
5,248 KB
testcase_04 AC 4 ms
5,248 KB
testcase_05 AC 4 ms
5,248 KB
testcase_06 AC 3 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 3 ms
5,248 KB
testcase_10 AC 2 ms
5,248 KB
testcase_11 AC 2 ms
5,248 KB
testcase_12 AC 2 ms
5,248 KB
testcase_13 AC 3 ms
5,248 KB
testcase_14 AC 2 ms
5,248 KB
testcase_15 AC 2 ms
5,248 KB
testcase_16 AC 2 ms
5,248 KB
testcase_17 AC 2 ms
5,248 KB
testcase_18 AC 2 ms
5,248 KB
testcase_19 AC 2 ms
5,248 KB
testcase_20 AC 2 ms
5,248 KB
testcase_21 AC 4,059 ms
10,624 KB
testcase_22 AC 4,067 ms
10,624 KB
testcase_23 AC 2 ms
5,248 KB
testcase_24 AC 2 ms
5,248 KB
testcase_25 AC 4,074 ms
10,624 KB
testcase_26 AC 4,075 ms
10,624 KB
testcase_27 AC 4,035 ms
10,624 KB
testcase_28 AC 3,444 ms
9,856 KB
testcase_29 AC 928 ms
5,632 KB
testcase_30 AC 978 ms
5,888 KB
testcase_31 AC 2 ms
5,248 KB
testcase_32 AC 2 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <utility>
#include <atcoder/modint>



const unsigned int MOD = 998244353;


long long N, M;
std::vector<atcoder::static_modint<MOD>> precalc;


class CompletelyMultiplicativePrefixSum{
public:
    using E = atcoder::static_modint<MOD>;
    using vecE = std::vector<E>;
    using i64 = long long;
    
    static std::pair<vecE, vecE> primesafe_sum(i64 n, i64 floor_sqrt_n){
        vecE fairies(floor_sqrt_n+1, 0);
        for(i64 i=0; i<=floor_sqrt_n; i++) fairies[i] = precalc[1] * i;
        vecE devils(floor_sqrt_n+1, 0);
        for(i64 i=1; i<=floor_sqrt_n; i++) devils[i] = precalc[1] * (n/i);
        return std::make_pair(std::move(fairies), std::move(devils));
    }
    static E primesafe_linearity_over_primepower(E fx, i64 pp){
        return fx;
    }
    static E optional_multiplicative_function(i64 p, i64 e){
        return precalc[e];
    }
private:

    i64 n;
    i64 sqrtn;
    std::vector<int> isprime_table;
    vecE primesafe_fairy;
    vecE fairies;
    vecE devils;

    CompletelyMultiplicativePrefixSum(i64 maxval){
        n = maxval;
        sqrtn = 0; while(sqrtn * sqrtn <= n) sqrtn++; sqrtn--;

        isprime_table.assign(sqrtn+1, 1);
        isprime_table[0] = isprime_table[1] = 0;
        
        {
            auto res_primesafe = primesafe_sum(n, sqrtn);
            fairies = std::move(res_primesafe.first);
            devils = std::move(res_primesafe.second);
            primesafe_fairy = fairies;
            for(int i=sqrtn; i>=1; i--) primesafe_fairy[i] -= primesafe_fairy[i-1];
            for(i64 p=2; p<=sqrtn; p++) fairies[p] -= fairies[1];
            for(i64 p=1; p<=sqrtn; p++) devils[p] -= fairies[1];
            fairies[1] = 0;
            primesafe_fairy[1] = 0;
        }

        for(i64 p=2; p<=sqrtn; p++){
            if(isprime_table[p] == 0) continue;
            for(i64 i=p*p; i<=sqrtn; i+=p) isprime_table[i] = 0;
            E prime_count_p_minus1 = fairies[p-1];
            for(i64 devil_id = 1; devil_id <= sqrtn; devil_id++){
                if(devil_id * p <= sqrtn){
                    devils[devil_id] -= primesafe_linearity_over_primepower(devils[devil_id * p] - prime_count_p_minus1, p);
                }
                else{
                    i64 tg_fairy = n / (devil_id * p);
                    if(tg_fairy < p) break;
                    devils[devil_id] -= primesafe_linearity_over_primepower(fairies[tg_fairy] - prime_count_p_minus1, p);
                }
            }
            for(i64 fairy_id = sqrtn/p; fairy_id >= p; fairy_id--){
                E dc = primesafe_linearity_over_primepower(fairies[fairy_id] - prime_count_p_minus1, p);
                i64 max_tg = std::min(fairy_id * p + p - 1, sqrtn);
                for(i64 tg_fairy = fairy_id * p; tg_fairy <= max_tg; tg_fairy++) fairies[tg_fairy] -= dc;
            }
        }
        
        for(i64 p=sqrtn; p>=2; p--){
            if(isprime_table[p] == 0) continue;
            E prime_count_p_minus1 = fairies[p-1];
            for(i64 fairy_id = p; fairy_id <= sqrtn/p; fairy_id++){
                E dc = (fairies[fairy_id] - prime_count_p_minus1) * primesafe_fairy[p];
                i64 max_tg = std::min(fairy_id * p + p - 1, sqrtn);
                for(i64 tg_fairy = fairy_id * p; tg_fairy <= max_tg; tg_fairy++) fairies[tg_fairy] += dc;
            }
            for(i64 devil_id = std::min(sqrtn, n / (p*p)); devil_id >= 1; devil_id--){
                if(devil_id * p <= sqrtn){
                    devils[devil_id] += (devils[devil_id * p] - prime_count_p_minus1) * primesafe_fairy[p];
                }
                else{
                    i64 tg_fairy = n / (devil_id * p);
                    devils[devil_id] += (fairies[tg_fairy] - prime_count_p_minus1) * primesafe_fairy[p];
                }
            }
        }

        for(i64 p=1; p<=sqrtn; p++) fairies[p] += 1;
        for(i64 p=1; p<=sqrtn; p++) devils[p] += 1;
    }

    E interpolation_sum(){
        vecE e_fairies(sqrtn+1, 0);
        vecE e_devils(sqrtn+1, 0);
        e_devils[1] = 1;
        std::vector<i64> power_p;
        power_p.resize(100);
        std::vector<E> coeff_diff;
        coeff_diff.resize(100);
        for(i64 p=2; p<=sqrtn; p++) if(isprime_table[p]){
            power_p[1] = p;
            for(int e = 2; p <= n / power_p[e-1]; e++){
                power_p[e] = power_p[e-1] * p;
                coeff_diff[e] = optional_multiplicative_function(p, e) - optional_multiplicative_function(p, e-1) * optional_multiplicative_function(p, 1);
                power_p[e+1] = n+1;
            }
            i64 max_fairy_id = sqrtn / power_p[2];
            for(i64 fairy_id = power_p[2]; fairy_id <= sqrtn; fairy_id++){
                i64 tg_fairy = fairy_id / power_p[2];
                for(int e = 2; tg_fairy >= 1; e++, tg_fairy /= p){
                    e_fairies[tg_fairy] += e_fairies[fairy_id] * coeff_diff[e];
                }
            }
            for(i64 devil_id = std::min(sqrtn, n / power_p[2]); devil_id >= 1; devil_id--){
                i64 devil_size = n / (devil_id * power_p[2]);
                for(int e = 2; devil_size >= 1; e++, devil_size /= p){
                    if(devil_size > sqrtn) e_devils[n / devil_size] += e_devils[devil_id] * coeff_diff[e];
                    else e_fairies[devil_size] += e_devils[devil_id] * coeff_diff[e];
                }
            }
        }
        E res = 0;
        for(i64 fairy_id = 1; fairy_id <= sqrtn; fairy_id++) res += fairies[fairy_id] * e_fairies[fairy_id];
        for(i64 devil_id = 1; devil_id <= sqrtn; devil_id++) res += devils[devil_id] * e_devils[devil_id];
        return res;
    }

public:

    static std::pair<vecE, vecE> solve(long long n){
        auto res = CompletelyMultiplicativePrefixSum(n);
        return std::make_pair(std::move(res.fairies), std::move(res.devils));
    }

    static E solve_general_multiplicative_sum(long long n){
        auto res = CompletelyMultiplicativePrefixSum(n);
        return res.interpolation_sum();
    }

};





#include <iostream>


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;

int main() {
    std::cin >> N >> M;
    precalc.assign(100, 1);
    for(int e=0; e<=100; e++) precalc[e] = atcoder::static_modint<MOD>(e+1).pow(N);
    auto ans = CompletelyMultiplicativePrefixSum::solve_general_multiplicative_sum(M);
    std::cout << ans.val() << std::endl;
    return 0;
}
0