結果
| 問題 |
No.1781 LCM
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2021-12-16 00:23:02 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 3,842 ms / 5,000 ms |
| コード長 | 10,870 bytes |
| コンパイル時間 | 1,107 ms |
| コンパイル使用メモリ | 106,964 KB |
| 最終ジャッジ日時 | 2025-01-26 23:27:00 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 31 |
ソースコード
#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;
}