結果
問題 | No.917 Make One With GCD |
ユーザー | alpha_virginis |
提出日時 | 2019-10-25 23:09:31 |
言語 | Rust (1.77.0 + proconio) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,022 bytes |
コンパイル時間 | 15,550 ms |
コンパイル使用メモリ | 404,340 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-13 07:15:55 |
合計ジャッジ時間 | 15,411 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | AC | 1 ms
6,812 KB |
testcase_02 | AC | 1 ms
6,816 KB |
testcase_03 | AC | 1 ms
6,940 KB |
testcase_04 | AC | 1 ms
6,944 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | WA | - |
testcase_08 | AC | 1 ms
6,940 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | AC | 1 ms
6,944 KB |
testcase_18 | WA | - |
testcase_19 | AC | 1 ms
6,944 KB |
testcase_20 | AC | 1 ms
6,944 KB |
testcase_21 | AC | 1 ms
6,944 KB |
testcase_22 | AC | 1 ms
6,944 KB |
testcase_23 | WA | - |
testcase_24 | AC | 2 ms
6,944 KB |
testcase_25 | WA | - |
testcase_26 | AC | 1 ms
6,940 KB |
testcase_27 | AC | 1 ms
6,940 KB |
testcase_28 | AC | 1 ms
6,944 KB |
testcase_29 | AC | 1 ms
6,940 KB |
testcase_30 | AC | 1 ms
6,940 KB |
testcase_31 | AC | 1 ms
6,940 KB |
testcase_32 | AC | 1 ms
6,940 KB |
testcase_33 | AC | 1 ms
6,944 KB |
testcase_34 | AC | 1 ms
6,940 KB |
testcase_35 | AC | 1 ms
6,944 KB |
コンパイルメッセージ
warning: unused variable: `d` --> src/main.rs:222:9 | 222 | for d in 0..pds[i].1 + 1 { | ^ help: if this is intentional, prefix it with an underscore: `_d` | = note: `#[warn(unused_variables)]` on by default warning: unused variable: `m` --> src/main.rs:250:9 | 250 | let m = 1_0000_1000; | ^ help: if this is intentional, prefix it with an underscore: `_m` warning: unused `Result` that must be used --> src/main.rs:306:5 | 306 | writeln!(buf, "{}", res); | ^^^^^^^^^^^^^^^^^^^^^^^^ | = note: this `Result` may be an `Err` variant, which should be handled = note: `#[warn(unused_must_use)]` on by default = note: this warning originates in the macro `writeln` (in Nightly builds, run with -Z macro-backtrace for more info)
ソースコード
/*------------------------------------------------------------------*/ /*------------------------- begin template -------------------------*/ /*------------------------------------------------------------------*/ // ref: tanakh <https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8> // diff: using Parser macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut parser = Parser::from_str($s); input_inner!{parser, $($r)*} }; (parser = $parser:ident, $($r:tt)*) => { input_inner!{$parser, $($r)*} }; (new_stdin_parser = $parser:ident, $($r:tt)*) => { let stdin = std::io::stdin(); let reader = std::io::BufReader::new(stdin.lock()); let mut $parser = Parser::new(reader); input_inner!{$parser, $($r)*} }; ($($r:tt)*) => { input!{new_stdin_parser = parser, $($r)*} }; } macro_rules! input_inner { ($parser:ident) => {}; ($parser:ident, ) => {}; ($parser:ident, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($parser, $t); input_inner!{$parser $($r)*} }; } macro_rules! read_value { ($parser:ident, ( $($t:tt),* )) => { ( $(read_value!($parser, $t)),* ) }; ($parser:ident, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($parser, $t)).collect::<Vec<_>>() }; ($parser:ident, chars) => { read_value!($parser, String).chars().collect::<Vec<char>>() }; ($parser:ident, char_) => { read_value!($parser, String).chars().collect::<Vec<char>>()[0] }; ($parser:ident, usize1) => { read_value!($parser, usize) - 1 }; ($parser:ident, i64_) => { $parser.fast_i64() }; ($parser:ident, usize_) => { $parser.fast_i64() as usize }; ($parser:ident, usize1_) => { ($parser.fast_i64() - 1) as usize }; ($parser:ident, $t:ty) => { $parser.next::<$t>().expect("Parse error") }; } use std::io; use std::io::BufRead; use std::str; // ref: tatsuya6502 <https://qiita.com/tatsuya6502/items/cd448486f7ef7b5b8c7e> // ref: wariuni <https://qiita.com/tatsuya6502/items/cd448486f7ef7b5b8c7e#comment-7040a5ae96305e884eb9> // diff: using std::io::BufRead::fill_buf() pub struct Parser<R> { pub reader: R, buf: Vec<u8>, pos: usize, } impl Parser<io::Empty> { pub fn from_str(s: &str) -> Parser<io::Empty> { Parser { reader: io::empty(), buf: s.as_bytes().to_vec(), pos: 0, } } } impl<R: BufRead> Parser<R> { pub fn new(reader: R) -> Parser<R> { Parser { reader: reader, buf: vec![], pos: 0, } } pub fn update_buf(&mut self) { self.buf.clear(); self.pos = 0; loop { let (len, complete) = { let buf2 = self.reader.fill_buf().unwrap(); self.buf.extend_from_slice(buf2); let len = buf2.len(); (len, buf2[len - 1] <= 0x20) }; self.reader.consume(len); if complete { break; } } } pub fn next<T: str::FromStr>(&mut self) -> Result<T, T::Err> { loop { let mut begin = self.pos; while begin < self.buf.len() && (self.buf[begin] <= 0x20) { begin += 1; } let mut end = begin; while end < self.buf.len() && (self.buf[end] > 0x20) { end += 1; } if begin != self.buf.len() { self.pos = end; return unsafe { str::from_utf8_unchecked(&self.buf[begin..end]) }.parse::<T>(); } else { self.update_buf(); } } } pub fn fast_i64(&mut self) -> i64 { loop { let mut begin = self.pos; while begin < self.buf.len() && (self.buf[begin] <= 0x20) { begin += 1; } if begin == self.buf.len() { self.update_buf(); continue; } let mut res = 0; let (is_positive, mut end) = match self.buf[begin] { b'+' => (true, begin + 1), b'-' => (false, begin + 1), _ => (true, begin), }; while end < self.buf.len() && (self.buf[end] > 0x20) { res = res * 10 + (self.buf[end] as i64 - '0' as i64); end += 1; } if begin != self.buf.len() { self.pos = end; return if is_positive { res } else { -res }; } else { self.update_buf(); } } } } #[allow(unused_imports)] use std::cmp::*; pub fn eratosthenes(n: usize) -> Vec<bool> { let n = n + 1; let mut res = vec![true; n]; res[0] = false; res[1] = false; for i in 2.. { if i * i > n { break; } if res[i] { let mut k = i * i; while k < n { res[k] = false; k += i; } } } res } pub fn prime_factorization(x: i64) -> Vec<(i64, usize)> { let mut x = x; let mut res = vec![]; for i in 2.. { if i * i > x { break; } let mut d = 0; while x % i == 0 { d += 1; x /= i; } if d != 0 { res.push((i, d)); } } if x != 1 { res.push((x, 1)); } res } pub fn divisors(x: i64) -> Vec<i64> { let pds = prime_factorization(x); // // eprintln!("pds = {:?}", pds); divisors_from_factors(&pds) } pub fn divisors_from_factors(pds: &Vec<(i64, usize)>) -> Vec<i64> { let mut res = vec![]; divisors_from_factors_sub(pds, 0, 1, &mut res); res } pub fn divisors_from_factors_sub(pds: &Vec<(i64, usize)>, i: usize, x: i64, res: &mut Vec<i64>) { if i == pds.len() { res.push(x); return; } let mut t = x; for d in 0..pds[i].1 + 1 { divisors_from_factors_sub(pds, i + 1, t, res); t *= pds[i].0; } } use std::collections::BTreeSet; fn main() { input! { new_stdin_parser = parser, } let res = solve(&mut parser); print!("{}", res); } /*------------------------------------------------------------------*/ /*-------------------------- end template --------------------------*/ /*------------------------------------------------------------------*/ use std::fmt::Write; fn solve<R: BufRead>(parser: &mut Parser<R>) -> String { let mut buf = String::new(); input! { parser = parser, n: usize, xs: [usize; n], } let m = 1_0000_1000; /* let mut pns = vec![0; m]; for i in 2..1_0000_1000 { if pns[i] == 0 { let mut k = i; while k < m { pns[k] += 1; k += i; } } } */ /* for i in 1_1000..m { if pns[i] == 0 { pns[i] = 1; } } */ /* for i in 0..20 { // eprintln!("pns[{}] = {}", i, pns[i]); } */ let mut set = BTreeSet::new(); for &x in &xs { let mut ps = prime_factorization(x as i64); for i in 0..ps.len() { ps[i].1 = 1; } let ys = divisors_from_factors(&ps); for &y in &ys { set.insert(y); } } let mut res = (1 << n) - 1; for &s in &set { if s == 1 { continue; } // eprintln!("s = {}", s); let mut count = 0; for &x in &xs { if x % s as usize == 0 { count += 1; } } // let t = pns[s as usize]; let t = prime_factorization(s as i64).len(); if t % 2 == 0 { res += (1 << count) - 1; } else { res -= (1 << count) - 1; } } writeln!(buf, "{}", res); buf }