結果
問題 | No.2211 Frequency Table of GCD |
ユーザー | sakikuroe |
提出日時 | 2023-02-10 22:08:26 |
言語 | Rust (1.77.0) |
結果 |
AC
|
実行時間 | 1,088 ms / 2,000 ms |
コード長 | 5,026 bytes |
コンパイル時間 | 5,379 ms |
コンパイル使用メモリ | 144,748 KB |
実行使用メモリ | 8,200 KB |
最終ジャッジ日時 | 2023-09-22 01:09:32 |
合計ジャッジ時間 | 17,161 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 503 ms
4,844 KB |
testcase_04 | AC | 462 ms
5,276 KB |
testcase_05 | AC | 608 ms
6,352 KB |
testcase_06 | AC | 552 ms
5,564 KB |
testcase_07 | AC | 710 ms
6,632 KB |
testcase_08 | AC | 12 ms
4,376 KB |
testcase_09 | AC | 10 ms
4,376 KB |
testcase_10 | AC | 27 ms
6,060 KB |
testcase_11 | AC | 17 ms
5,000 KB |
testcase_12 | AC | 29 ms
6,364 KB |
testcase_13 | AC | 427 ms
5,048 KB |
testcase_14 | AC | 609 ms
5,932 KB |
testcase_15 | AC | 521 ms
5,216 KB |
testcase_16 | AC | 574 ms
5,616 KB |
testcase_17 | AC | 590 ms
6,076 KB |
testcase_18 | AC | 881 ms
7,948 KB |
testcase_19 | AC | 880 ms
7,904 KB |
testcase_20 | AC | 878 ms
7,908 KB |
testcase_21 | AC | 879 ms
7,836 KB |
testcase_22 | AC | 877 ms
7,840 KB |
testcase_23 | AC | 555 ms
4,376 KB |
testcase_24 | AC | 1,088 ms
8,200 KB |
testcase_25 | AC | 15 ms
7,088 KB |
testcase_26 | AC | 1 ms
4,380 KB |
testcase_27 | AC | 862 ms
7,888 KB |
testcase_28 | AC | 1,087 ms
8,136 KB |
ソースコード
#[macro_export] macro_rules! read_line { ($($xs: tt)*) => { let mut buf = String::new(); std::io::stdin().read_line(&mut buf).unwrap(); let mut iter = buf.split_whitespace(); expand!(iter, $($xs)*); }; } #[macro_export] macro_rules! expand { ($iter: expr,) => {}; ($iter: expr, mut $var: ident : $type: tt, $($xs: tt)*) => { let mut $var = value!($iter, $type); expand!($iter, $($xs)*); }; ($iter: expr, $var: ident : $type: tt, $($xs: tt)*) => { let $var = value!($iter, $type); expand!($iter, $($xs)*); }; } #[macro_export] macro_rules! value { ($iter:expr, ($($type: tt),*)) => { ($(value!($iter, $type)),*) }; ($iter: expr, [$type: tt; $len: expr]) => { (0..$len).map(|_| value!($iter, $type)).collect::<Vec<_>>() }; ($iter: expr, Chars) => { value!($iter, String).unwrap().chars().collect::<Vec<_>>() }; ($iter: expr, $type: ty) => { if let Some(v) = $iter.next() { v.parse::<$type>().ok() } else { None } }; } use std::{fmt, ops}; const MOD: usize = 998244353; // 119 * (1 << 23) + 1 #[derive(Copy, Clone, Debug, PartialEq, Eq)] pub struct ModInt { value: usize, } impl ModInt { pub fn new(value: usize) -> ModInt { ModInt { value: value % MOD } } pub fn value(&self) -> usize { self.value } pub fn inverse(&self) -> ModInt { // (a, b) -> (x, y) s.t. a * x + b * y = gcd(a, b) fn extended_gcd(a: isize, b: isize) -> (isize, isize) { if (a, b) == (1, 0) { (1, 0) } else { let (x, y) = extended_gcd(b, a % b); (y, x - (a / b) * y) } } let (x, _y) = extended_gcd(self.value() as isize, MOD as isize); ModInt::new((MOD as isize + x) as usize) } // a^n pub fn pow(&self, mut n: usize) -> ModInt { let mut res = ModInt::new(1); let mut x = *self; while n > 0 { if n % 2 == 1 { res *= x; } x *= x; n /= 2; } res } } impl ops::Add for ModInt { type Output = ModInt; fn add(self, other: Self) -> Self { ModInt::new(self.value + other.value) } } impl ops::Sub for ModInt { type Output = ModInt; fn sub(self, other: Self) -> Self { ModInt::new(MOD + self.value - other.value) } } impl ops::Mul for ModInt { type Output = ModInt; fn mul(self, other: Self) -> Self { ModInt::new(self.value * other.value) } } impl ops::Div for ModInt { type Output = ModInt; fn div(self, other: Self) -> Self { self * other.inverse() } } impl ops::AddAssign for ModInt { fn add_assign(&mut self, other: Self) { *self = *self + other; } } impl ops::SubAssign for ModInt { fn sub_assign(&mut self, other: Self) { *self = *self - other; } } impl ops::MulAssign for ModInt { fn mul_assign(&mut self, other: Self) { *self = *self * other; } } impl ops::DivAssign for ModInt { fn div_assign(&mut self, other: Self) { *self = *self / other; } } // n! pub fn factorial(n: usize) -> ModInt { (1..=n).fold(ModInt::new(1), |x, y| x * ModInt::new(y)) } // nPr pub fn permutation(n: usize, r: usize) -> ModInt { if n < r { ModInt::new(0) } else { (n - r + 1..=n).fold(ModInt::new(1), |x, y| x * ModInt::new(y)) } } // nCr pub fn combination(n: usize, r: usize) -> ModInt { if n < r { ModInt::new(0) } else { permutation(n, r) / factorial(r) } } // nHr pub fn homogeneous(n: usize, r: usize) -> ModInt { combination(n + r - 1, r) } // Catalan number pub fn catalan(n: usize) -> ModInt { combination(2 * n, n) / ModInt::new(n + 1) } impl fmt::Display for ModInt { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { write!(f, "{}", self.value()) } } pub fn gen_divisors(n: usize) -> Vec<usize> { let mut res = vec![]; for i in (1..).take_while(|&x| x * x <= n) { if n % i == 0 { res.push(i); if i * i < n { res.push(n / i); } } } res.sort(); res } fn main() { read_line!(n: usize, m: usize,); let n = n.unwrap(); let m = m.unwrap(); read_line!(a: [usize; n],); let a = a.into_iter().map(|x| x.unwrap()).collect::<Vec<_>>(); let mut cnt = vec![0; m + 1]; for i in 0..n { for d in gen_divisors(a[i]) { cnt[d] += 1; } } let mut ans = vec![ModInt::new(0); m + 1]; for i in 1..=m { ans[i] = ModInt::new(2).pow(cnt[i]) - ModInt::new(1); } for i in (1..=m).rev() { for d in gen_divisors(i) { if d < i { ans[d] = ans[d] - ans[i]; } } } for i in 1..=m { println!("{}", ans[i]); } }