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