結果
問題 | No.1781 LCM |
ユーザー | akakimidori |
提出日時 | 2021-12-10 13:44:07 |
言語 | Rust (1.83.0 + proconio) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 10,927 bytes |
コンパイル時間 | 12,020 ms |
コンパイル使用メモリ | 397,740 KB |
実行使用メモリ | 36,236 KB |
最終ジャッジ日時 | 2024-07-18 07:37:41 |
合計ジャッジ時間 | 39,061 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 1 ms
5,376 KB |
testcase_09 | AC | 1 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 1 ms
5,376 KB |
testcase_13 | AC | 1 ms
5,376 KB |
testcase_14 | AC | 1 ms
5,376 KB |
testcase_15 | AC | 1 ms
5,376 KB |
testcase_16 | AC | 1 ms
5,376 KB |
testcase_17 | AC | 1 ms
5,376 KB |
testcase_18 | AC | 1 ms
5,376 KB |
testcase_19 | AC | 1 ms
5,376 KB |
testcase_20 | AC | 1 ms
5,376 KB |
testcase_21 | AC | 4,131 ms
36,236 KB |
testcase_22 | AC | 4,163 ms
36,160 KB |
testcase_23 | AC | 1 ms
5,376 KB |
testcase_24 | AC | 1 ms
5,376 KB |
testcase_25 | AC | 4,143 ms
36,228 KB |
testcase_26 | AC | 4,154 ms
36,220 KB |
testcase_27 | AC | 4,234 ms
35,964 KB |
testcase_28 | AC | 3,436 ms
32,336 KB |
testcase_29 | AC | 867 ms
14,012 KB |
testcase_30 | AC | 908 ms
14,464 KB |
testcase_31 | AC | 1 ms
5,376 KB |
testcase_32 | AC | 1 ms
5,376 KB |
コンパイルメッセージ
warning: unused variable: `sum_large` --> src/main.rs:331:13 | 331 | let mut sum_large: Vec<Option<(usize, usize, M)>> = vec![None; sqrt + 1]; | ^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_sum_large` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `sum_small` --> src/main.rs:332:13 | 332 | let mut sum_small: Vec<Option<(usize, usize, M)>> = vec![None; sqrt + 1]; | ^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_sum_small` warning: unused variable: `i` --> src/main.rs:336:10 | 336 | for (i, &p) in prime.iter().enumerate() { | ^ help: if this is intentional, prefix it with an underscore: `_i` warning: value assigned to `l` is never read --> src/main.rs:348:17 | 348 | l = r + 1; | ^ | = help: maybe it is overwritten before being read? = note: `#[warn(unused_assignments)]` on by default warning: variable does not need to be mutable --> src/main.rs:331:9 | 331 | let mut sum_large: Vec<Option<(usize, usize, M)>> = vec![None; sqrt + 1]; | ----^^^^^^^^^ | | | help: remove this `mut` | = note: `#[warn(unused_mut)]` on by default warning: variable does not need to be mutable --> src/main.rs:332:9 | 332 | let mut sum_small: Vec<Option<(usize, usize, M)>> = vec![None; sqrt + 1]; | ----^^^^^^^^^ | | | help: remove this `mut` warning: type alias `Map` is never used --> src/main.rs:297:6 | 297 | type Map<K, V> = HashMap<K, V>; | ^^^ | = note: `#[warn(dead_code)]` on by default warning: function `naive` is never used --> src/main.rs:397:4 | 397 | fn naive(n: usize, m: usize) { | ^^^^^
ソースコード
// 初期化配列 // 初期値とサイズを与えて適当にやる系 // new(size, zero): zero埋めした長さsizeの配列を返す // init(&mut self): 初期化 // index(mut) でアクセスしたときその履歴を溜め込む // それ以外でアクセスすると死ぬので注意 // // 考えるべきこと // 1. deref で dataへアクセスできるようにしていいか // derefmut はダメ // 2. 今のままだと二次元配列の初期化とかには対応できない // なんか方法を考えたい // ---------- begin init array ---------- #[derive(Clone)] pub struct InitArray<T> { data: Vec<T>, list: Vec<usize>, zero: T, } impl<T: Copy> InitArray<T> { pub fn new(zero: T, size: usize) -> Self { InitArray { data: vec![zero; size], list: vec![], zero: zero, } } pub fn init_with<F>(&mut self, mut f: F) where F: FnMut(usize, T), { for x in self.list.drain(..) { let v = std::mem::replace(&mut self.data[x], self.zero); f(x, v); } } } impl<T> std::ops::Index<usize> for InitArray<T> { type Output = T; fn index(&self, pos: usize) -> &Self::Output { &self.data[pos] } } impl<T: PartialEq> std::ops::IndexMut<usize> for InitArray<T> { fn index_mut(&mut self, pos: usize) -> &mut Self::Output { if self.data[pos] == self.zero { self.list.push(pos); } &mut self.data[pos] } } // ---------- end init array ---------- // ---------- begin prime count ---------- // 処理が終わった時 // large[i]: pi(floor(n / i)) // small[i]: pi(i) // となっている // O(N^(3/4)/log N) pub fn prime_count(n: usize) -> (Vec<usize>, Vec<usize>) { if n <= 1 { return (vec![0, 0], vec![0, 0]); } let sqrt = (1..).find(|p| p * p > n).unwrap() - 1; let mut large = vec![0; sqrt + 1]; let mut small = vec![0; sqrt + 1]; for (i, (large, small)) in large.iter_mut().zip(&mut small).enumerate().skip(1) { *large = n / i - 1; *small = i - 1; } for p in 2..=sqrt { if small[p] == small[p - 1] { continue; } let pi = small[p] - 1; let q = p * p; for i in 1..=sqrt.min(n / q) { large[i] -= *large.get(i * p).unwrap_or_else(|| &small[n / (i * p)]) - pi; } for i in (q..=sqrt).rev() { small[i] -= small[i / p] - pi; } } (small, large) } // ---------- end prime count ---------- // ---------- begin enumerate prime ---------- fn enumerate_prime<F>(n: usize, mut f: F) where F: FnMut(usize), { assert!(1 <= n && n <= 5 * 10usize.pow(8)); let batch = (n as f64).sqrt().ceil() as usize; let mut is_prime = vec![true; batch + 1]; for i in (2..).take_while(|p| p * p <= batch) { if is_prime[i] { let mut j = i * i; while let Some(p) = is_prime.get_mut(j) { *p = false; j += i; } } } let mut prime = vec![]; for (i, p) in is_prime.iter().enumerate().skip(2) { if *p && i <= n { f(i); prime.push(i); } } let mut l = batch + 1; while l <= n { let r = std::cmp::min(l + batch, n + 1); is_prime.clear(); is_prime.resize(r - l, true); for &p in prime.iter() { let mut j = (l + p - 1) / p * p - l; while let Some(is_prime) = is_prime.get_mut(j) { *is_prime = false; j += p; } } for (i, _) in is_prime.iter().enumerate().filter(|p| *p.1) { f(i + l); } l += batch; } } // ---------- end enumerate prime ---------- use std::marker::*; use std::ops::*; pub trait Modulo { fn modulo() -> u32; } pub struct ConstantModulo<const M: u32>; impl<const M: u32> Modulo for ConstantModulo<{ M }> { fn modulo() -> u32 { M } } pub struct ModInt<T>(u32, PhantomData<T>); impl<T> PartialEq for ModInt<T> { fn eq(&self, rhs: &Self) -> bool { self.0 == rhs.0 } } impl<T> Clone for ModInt<T> { fn clone(&self) -> Self { Self::new_unchecked(self.0) } } impl<T> Copy for ModInt<T> {} impl<T: Modulo> Add for ModInt<T> { type Output = ModInt<T>; fn add(self, rhs: Self) -> Self::Output { let mut v = self.0 + rhs.0; if v >= T::modulo() { v -= T::modulo(); } Self::new_unchecked(v) } } impl<T: Modulo> AddAssign for ModInt<T> { fn add_assign(&mut self, rhs: Self) { *self = *self + rhs; } } impl<T: Modulo> Sub for ModInt<T> { type Output = ModInt<T>; fn sub(self, rhs: Self) -> Self::Output { let mut v = self.0 - rhs.0; if self.0 < rhs.0 { v += T::modulo(); } Self::new_unchecked(v) } } impl<T: Modulo> SubAssign for ModInt<T> { fn sub_assign(&mut self, rhs: Self) { *self = *self - rhs; } } impl<T: Modulo> Mul for ModInt<T> { type Output = ModInt<T>; fn mul(self, rhs: Self) -> Self::Output { let v = self.0 as u64 * rhs.0 as u64 % T::modulo() as u64; Self::new_unchecked(v as u32) } } impl<T: Modulo> MulAssign for ModInt<T> { fn mul_assign(&mut self, rhs: Self) { *self = *self * rhs; } } impl<T: Modulo> Neg for ModInt<T> { type Output = ModInt<T>; fn neg(self) -> Self::Output { if self.is_zero() { Self::zero() } else { Self::new_unchecked(T::modulo() - self.0) } } } impl<T> std::fmt::Display for ModInt<T> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl<T> std::fmt::Debug for ModInt<T> { fn fmt<'a>(&self, f: &mut std::fmt::Formatter<'a>) -> std::fmt::Result { write!(f, "{}", self.0) } } impl<T> Default for ModInt<T> { fn default() -> Self { Self::zero() } } impl<T: Modulo> std::str::FromStr for ModInt<T> { type Err = std::num::ParseIntError; fn from_str(s: &str) -> Result<Self, Self::Err> { let val = s.parse::<u32>()?; Ok(ModInt::new(val)) } } impl<T: Modulo> From<usize> for ModInt<T> { fn from(val: usize) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as usize) as u32) } } impl<T: Modulo> From<u64> for ModInt<T> { fn from(val: u64) -> ModInt<T> { ModInt::new_unchecked((val % T::modulo() as u64) as u32) } } impl<T> ModInt<T> { pub fn new_unchecked(n: u32) -> Self { ModInt(n, PhantomData) } pub fn zero() -> Self { ModInt::new_unchecked(0) } pub fn one() -> Self { ModInt::new_unchecked(1) } pub fn is_zero(&self) -> bool { self.0 == 0 } } impl<T: Modulo> ModInt<T> { pub fn new(d: u32) -> Self { ModInt::new_unchecked(d % T::modulo()) } pub fn pow(&self, mut n: u64) -> Self { let mut t = Self::one(); let mut s = *self; while n > 0 { if n & 1 == 1 { t *= s; } s *= s; n >>= 1; } t } } type M = ModInt<ConstantModulo<998_244_353>>; use std::collections::*; type Map<K, V> = HashMap<K, V>; fn read() -> (usize, usize) { let mut s = String::new(); std::io::stdin().read_line(&mut s).unwrap(); let a = s .trim() .split_whitespace() .flat_map(|s| s.parse()) .collect::<Vec<_>>(); (a[0], a[1]) } fn solve(n: usize, m: usize) { let mut pow = vec![M::zero(); 40 + 1]; for i in 1..=40 { pow[i] = M::from(i).pow(n as u64); } let pow = pow.windows(2).map(|p| p[1] - p[0]).collect::<Vec<_>>(); let sqrt = (2..).find(|p| p * p > m).unwrap() - 1; let pi = prime_count(m); let pi = |x: usize| -> usize { if x <= sqrt { return pi.0[x]; } let q = m / x; pi.1[q] }; let mut prime = vec![]; enumerate_prime(sqrt + 1000, |p| prime.push(p)); let mut large = InitArray::new(M::zero(), sqrt + 1); let mut small = InitArray::new(M::zero(), sqrt + 1); let mut next_large = InitArray::new(M::zero(), sqrt + 1); let mut next_small = InitArray::new(M::zero(), sqrt + 1); let mut sum_large: Vec<Option<(usize, usize, M)>> = vec![None; sqrt + 1]; let mut sum_small: Vec<Option<(usize, usize, M)>> = vec![None; sqrt + 1]; large[1] = M::one(); let mut ans = M::zero(); let mut last = M::zero(); for (i, &p) in prime.iter().enumerate() { let mut calc = |m: usize, v: M| { ans += M::from(m) * v; let mut l = p; let mut q = m / l; let mut add = 0usize; let mut pl = pi(l - 1); while q > 0 { let r = m / q; let pr = pi(r); add += q * (pr - pl); pl = pr; l = r + 1; q -= 1; } last += M::from(add) * v; }; large.init_with(|d, v| { let m = m / d; if p * p > m { calc(m, v); } else { let mut pp = 1; let mut k = 0; while d * pp <= sqrt { let v = v * pow[k]; let d = d * pp; next_large[d] += v; k += 1; pp *= p; } let mut m = m / pp; while m > 0 { let v = v * pow[k]; next_small[m] += v; m /= p; k += 1; } } }); small.init_with(|m, v| { if p * p > m { calc(m, v); } else { let mut m = m; let mut k = 0; while m > 0 { let v = v * pow[k]; next_small[m] += v; m /= p; k += 1; } } }); std::mem::swap(&mut small, &mut next_small); std::mem::swap(&mut large, &mut next_large); } ans += pow[1] * last; println!("{}", ans); } fn naive(n: usize, m: usize) { let mut dp = vec![M::one(); m + 1]; enumerate_prime(m, |p| { for i in 1..=(m / p) { dp[p * i] = dp[p * i] + dp[i]; } }); for dp in dp.iter_mut() { *dp = dp.pow(n as u64); } enumerate_prime(m, |p| { for i in (1..=(m / p)).rev() { dp[p * i] = dp[p * i] - dp[i]; } }); let mut ans = M::zero(); for i in 1..=m { ans += M::from(m / i) * dp[i]; } println!("{}", ans); } fn main() { let (n, m) = read(); solve(n, m); }