結果

問題 No.1781 LCM
ユーザー 👑 NachiaNachia
提出日時 2021-12-16 00:23:02
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 3,777 ms / 5,000 ms
コード長 10,870 bytes
コンパイル時間 1,190 ms
コンパイル使用メモリ 106,708 KB
実行使用メモリ 10,624 KB
最終ジャッジ日時 2024-09-26 06:38:10
合計ジャッジ時間 25,926 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 4 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 4 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 1 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 2 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 1 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 3,724 ms
10,496 KB
testcase_22 AC 3,777 ms
10,624 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 3,741 ms
10,496 KB
testcase_26 AC 3,743 ms
10,496 KB
testcase_27 AC 3,712 ms
10,624 KB
testcase_28 AC 3,205 ms
9,728 KB
testcase_29 AC 848 ms
5,760 KB
testcase_30 AC 893 ms
5,760 KB
testcase_31 AC 2 ms
5,376 KB
testcase_32 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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



#include <iostream>
#include <functional>


class PrimeCounting{
    using i64 = long long;
    i64 n;
    i64 sqrtn;
    std::vector<i64> prefix_sum_devil;
    std::vector<i64> prefix_sum_fairy;

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

        prefix_sum_fairy.assign(sqrtn+1, 0);
        prefix_sum_fairy[0] = 0;
        for(i64 i=1; i<=sqrtn; i++) prefix_sum_fairy[i] = i-1;
        prefix_sum_devil.assign(sqrtn+1, 0);
        for(i64 i=1; i<=sqrtn; i++) prefix_sum_devil[i] = n/i-1;

        for(i64 p=2; p<=sqrtn; p++){
            i64 prime_count_p = prefix_sum_fairy[p];
            i64 prime_count_p_minus1 = prefix_sum_fairy[p-1];
            if(prime_count_p == prime_count_p_minus1) continue;
            for(i64 devil_id = 1; devil_id <= sqrtn; devil_id++){
                if(devil_id * p <= sqrtn){
                    prefix_sum_devil[devil_id] -= prefix_sum_devil[devil_id * p] - prime_count_p_minus1;
                }
                else{
                    i64 tg_fairy = n / (devil_id * p);
                    if(tg_fairy < p) break;
                    prefix_sum_devil[devil_id] -= prefix_sum_fairy[tg_fairy] - prime_count_p_minus1;
                }
            }
            for(i64 fairy_id = sqrtn/p; fairy_id >= p; fairy_id--){
                i64 dc = prefix_sum_fairy[fairy_id] - prime_count_p_minus1;
                i64 max_tg = std::min(fairy_id * p + p - 1, sqrtn);
                for(i64 tg_fairy = fairy_id * p; tg_fairy <= max_tg; tg_fairy++) prefix_sum_fairy[tg_fairy] -= dc;
            }
        }
    }

public:

    static long long solve(long long n){
        if(n <= 1) return 0;
        auto res = PrimeCounting(n);
        return res.prefix_sum_devil[1];
    }

    static std::pair<std::vector<long long>, std::vector<long long>> solve_sqrt_decomposition(long long n){
        if(n <= 1) return std::make_pair(std::vector<long long>{0}, std::vector<long long>{0});
        auto res = PrimeCounting(n);
        return std::make_pair(std::move(res.prefix_sum_fairy), std::move(res.prefix_sum_devil));
    }
};


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 E(e+1).pow(N);
        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--;

        //std::cout << "sqrtn = " << sqrtn << std::endl;

        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;
        }

        //std::cout << "CompletelyMultiplicativePrefixSum layer 0" << std::endl;
        //std::cout << "fairy : [ "; for(auto a : fairies) std::cout << a.val() << " "; std::cout << "]" << std::endl;
        //std::cout << "devil : [ "; for(auto a : devils) std::cout << a.val() << " "; std::cout << "]" << std::endl;

        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;
            }
        }

        //std::cout << "CompletelyMultiplicativePrefixSum layer 1" << std::endl;
        //std::cout << "fairy : [ "; for(auto a : fairies) std::cout << a.val() << " "; std::cout << "]" << std::endl;
        //std::cout << "devil : [ "; for(auto a : devils) std::cout << a.val() << " "; std::cout << "]" << std::endl;
        
        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;
        
        //std::cout << "CompletelyMultiplicativePrefixSum layer 2" << std::endl;
        //std::cout << "fairy : [ "; for(auto a : fairies) std::cout << a.val() << " "; std::cout << "]" << std::endl;
        //std::cout << "devil : [ "; for(auto a : devils) std::cout << a.val() << " "; std::cout << "]" << std::endl;
    }

    E interpolation_sum(){

        /*
        std::vector<i64> primes;
        for(int p=2; p<=sqrtn; p++) if(isprime_table[p]) primes.push_back(p);

        std::function<E(i64,int,E)>rec=[&](i64 pn,int beg,E coef){
            if(coef==0)return E(0);
            E ret=coef*(pn>sqrtn?devils[n/pn]:fairies[pn]);
            for(int i=beg;i<(int)primes.size();i++){
                i64 p=primes[i],nn=pn/p/p;
                if(nn==0)break;
                for(int e=2;nn;nn/=p,e++){
                    ret+=rec(nn,i+1,coef*(optional_multiplicative_function(p,e)-optional_multiplicative_function(p,1)*optional_multiplicative_function(p,e-1)));
                }
            }
            return ret;
        };
        return rec(n,0,1);
        */
        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){
                    //std::cout << "e = " << e << std::endl;
                    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];
                }
                //std::cout << "devil_id = " << devil_id << std::endl;
            }
            //std::cout << "p = " << p << std::endl;
            //std::cout << "fairy : [ "; for(auto a : e_fairies) std::cout << a.val() << " "; std::cout << "]" << std::endl;
            //std::cout << "devil : [ "; for(auto a : e_devils) std::cout << a.val() << " "; std::cout << "]" << std::endl;
        }
        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