結果
問題 | No.1164 GCD Products hard |
ユーザー | nebocco |
提出日時 | 2021-02-26 15:17:44 |
言語 | Rust (1.77.0 + proconio) |
結果 |
AC
|
実行時間 | 109 ms / 2,500 ms |
コード長 | 10,656 bytes |
コンパイル時間 | 27,445 ms |
コンパイル使用メモリ | 399,864 KB |
実行使用メモリ | 8,448 KB |
最終ジャッジ日時 | 2024-10-02 08:32:04 |
合計ジャッジ時間 | 17,562 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
6,400 KB |
testcase_01 | AC | 85 ms
6,784 KB |
testcase_02 | AC | 60 ms
5,760 KB |
testcase_03 | AC | 23 ms
5,248 KB |
testcase_04 | AC | 19 ms
5,248 KB |
testcase_05 | AC | 75 ms
6,528 KB |
testcase_06 | AC | 80 ms
7,040 KB |
testcase_07 | AC | 82 ms
7,552 KB |
testcase_08 | AC | 80 ms
7,424 KB |
testcase_09 | AC | 61 ms
5,888 KB |
testcase_10 | AC | 22 ms
5,248 KB |
testcase_11 | AC | 61 ms
6,144 KB |
testcase_12 | AC | 88 ms
7,168 KB |
testcase_13 | AC | 54 ms
5,248 KB |
testcase_14 | AC | 42 ms
5,888 KB |
testcase_15 | AC | 81 ms
7,552 KB |
testcase_16 | AC | 50 ms
6,272 KB |
testcase_17 | AC | 72 ms
6,144 KB |
testcase_18 | AC | 66 ms
5,888 KB |
testcase_19 | AC | 19 ms
5,248 KB |
testcase_20 | AC | 36 ms
5,248 KB |
testcase_21 | AC | 95 ms
7,680 KB |
testcase_22 | AC | 1 ms
5,248 KB |
testcase_23 | AC | 62 ms
8,320 KB |
testcase_24 | AC | 109 ms
8,448 KB |
testcase_25 | AC | 1 ms
5,248 KB |
testcase_26 | AC | 1 ms
5,248 KB |
testcase_27 | AC | 1 ms
5,248 KB |
testcase_28 | AC | 1 ms
5,248 KB |
ソースコード
fn main() { let mut io = IO::new(); input!{ from io, a: i64, b: i64, n: i64 } const MOD: i64 = 1_000_000_007; let sieve = atkin_sieve(b as usize); let mut ans = 1; let mut memo = vec![0; 3000]; for p in sieve { let mut v = p; let mut c = modpow_memo(b / v - (a - 1) / v, n, MOD - 1, &mut memo); while v <= b { v *= p; c = (c + modpow_memo(b / v - (a - 1) / v, n, MOD - 1, &mut memo)) % (MOD - 1); } ans = ans * modpow(p, c, MOD) % MOD; } io.println(ans); } pub fn modpow(mut x: i64, mut y: i64, modulo: i64) -> i64 { x %= modulo; if x == 0 { return 0; } let mut ret = 1; let mut cur = x; while y > 0 { if y & 1 > 0 { ret = ret * cur % modulo; } cur = cur * cur % modulo; y >>= 1; } ret } pub fn modpow_memo(mut x: i64, mut y: i64, modulo: i64, memo: &mut Vec<i64>) -> i64 { x %= modulo; if x == 0 { return 0; } let xu = x as usize; if xu < memo.len() && memo[xu] > 0 { return memo[xu]; } let mut ret = 1; let mut cur = x; while y > 0 { if y & 1 > 0 { ret = ret * cur % modulo; } cur = cur * cur % modulo; y >>= 1; } if xu < memo.len() { memo[xu] = ret; } ret } pub fn atkin_sieve(n: usize) -> Vec<i64> { let mut sieve = BitSet::new(n+1); let lim = (n as f64).sqrt() as usize + 1; for z in (1..6).step_by(4) { for y in (z..lim).step_by(6) { for x in 1..lim { if 4 * x * x + y * y > n { break; } sieve.flip(4 * x * x + y * y); } for x in (y+1..lim).step_by(2) { if 3 * x * x - y * y > n { break; } sieve.flip(3 * x * x - y * y); } } } for z in (2..5).step_by(2) { for y in (z..lim).step_by(6) { for x in (1..lim).step_by(2) { if 3 * x * x + y * y > n { break; } sieve.flip(3 * x * x + y * y); } for x in (y+1..lim).step_by(2) { if 3 * x * x - y * y > n { break; } sieve.flip(3 * x * x - y * y); } } } for z in 1..3 { for y in (3..lim).step_by(6) { for x in (z..lim).step_by(3) { if 4 * x * x + y * y > n { break; } sieve.flip(4 * x * x + y * y); } } } for i in 5..lim { if sieve.access(i) { for j in (i*i..n+1).step_by(i*i) { sieve.set(j, false); } } } sieve.set(2, true); sieve.set(3, true); sieve.collect().into_iter().map(|x| x as i64).collect() } use std::ops::{Shl, Shr, BitAnd, BitOr, BitXor, Not}; #[derive(Clone)] pub struct BitSet { data: Vec<u32>, size: usize } impl BitSet { pub fn new(size: usize) -> Self { let data = vec![0; (size >> 5) + 1]; BitSet{ data, size } } pub fn fill(&mut self) { self.data.iter_mut().for_each(|x| *x = 0xffffffff ); } pub fn access(&self, pos: usize) -> bool { (self.data[pos >> 5] >> (pos & 31)) & 1 == 1 } pub fn set(&mut self, pos: usize, v: bool) { if v { self.data[pos >> 5] |= 1 << (pos & 31); } else { self.data[pos >> 5] &= !(1 << (pos & 31)); } } pub fn flip(&mut self, pos: usize) { self.data[pos >> 5] ^= 1 << (pos & 31); } pub fn collect(&self) -> Vec<u64> { (0..self.size) .filter(|&i| self.access(i)) .map(|x| x as u64) .collect::<Vec<u64>>() } fn resize(&mut self, l: usize) { if self.size > l { return; } self.data.resize((l >> 5) + 1, 0); self.size = l; } } impl BitAnd for BitSet { type Output = Self; fn bitand(mut self, rhs: Self) -> Self { let m = std::cmp::max(self.size, rhs.size); self.resize(m); for (u, v) in self.data.iter_mut().zip(rhs.data.iter()) { *u &= v; } self } } impl BitOr for BitSet { type Output = Self; fn bitor(mut self, rhs: Self) -> Self { let m = std::cmp::max(self.size, rhs.size); self.resize(m); for (u, v) in self.data.iter_mut().zip(rhs.data.iter()) { *u |= v; } self } } impl BitXor for BitSet { type Output = Self; fn bitxor(mut self, rhs: Self) -> Self { let m = std::cmp::max(self.size, rhs.size); self.resize(m); for (u, v) in self.data.iter_mut().zip(rhs.data.iter()) { *u ^= v; } self } } impl Not for BitSet { type Output = Self; fn not(mut self) -> Self { for u in self.data.iter_mut() { *u = !*u; } self } } impl Shr<usize> for BitSet { type Output = Self; fn shr(mut self, rhs: usize) -> Self::Output { let big = rhs >> 5; let sml = (rhs & 31) as u32; let mask = (1 << sml) - 1; for i in 0..self.data.len() { self.data[i] = if i + big < self.data.len() { self.data[i+big] } else { 0 }; } let mut r = 0; for i in (0..self.data.len()).rev() { let u = self.data[i]; self.data[i] = (u & !mask | r).rotate_right(sml); r = u & mask; } self } } impl Shl<usize> for BitSet { type Output = Self; fn shl(mut self, rhs: usize) -> Self::Output { let n = self.data.len(); let big = rhs >> 5; let sml = (rhs & 31) as u32; let mask = (1 << sml) - 1; for i in (0..n).rev() { self.data[i] = if i >= big { self.data[i-big] } else { 0 }; } let mut r = 0; for i in 0..n { let u = self.data[i].rotate_left(sml); self.data[i] = u & !mask | r; r = u & mask; } self.data[n-1] &= (1 << (self.size & 31)) - 1; self } } // ------------ io module start ------------ use std::io::{stdout, BufWriter, Read, StdoutLock, Write}; pub struct IO { iter: std::str::SplitAsciiWhitespace<'static>, buf: BufWriter<StdoutLock<'static>>, } impl IO { pub fn new() -> Self { let mut input = String::new(); std::io::stdin().read_to_string(&mut input).unwrap(); let input = Box::leak(input.into_boxed_str()); let out = Box::new(stdout()); IO { iter: input.split_ascii_whitespace(), buf: BufWriter::new(Box::leak(out).lock()), } } fn scan_str(&mut self) -> &'static str { self.iter.next().unwrap() } pub fn scan<T: Scan>(&mut self) -> <T as Scan>::Output { <T as Scan>::scan(self) } pub fn scan_vec<T: Scan>(&mut self, n: usize) -> Vec<<T as Scan>::Output> { (0..n).map(|_| self.scan::<T>()).collect() } pub fn print<T: Print>(&mut self, x: T) { <T as Print>::print(self, x); } pub fn println<T: Print>(&mut self, x: T) { self.print(x); self.print("\n"); } pub fn iterln<T: Print, I: Iterator<Item = T>>(&mut self, mut iter: I, delim: &str) { if let Some(v) = iter.next() { self.print(v); for v in iter { self.print(delim); self.print(v); } } self.print("\n"); } pub fn flush(&mut self) { self.buf.flush().unwrap(); } } impl Default for IO { fn default() -> Self { Self::new() } } pub trait Scan { type Output; fn scan(io: &mut IO) -> Self::Output; } macro_rules! impl_scan { ($($t:tt),*) => { $( impl Scan for $t { type Output = Self; fn scan(s: &mut IO) -> Self::Output { s.scan_str().parse().unwrap() } } )* }; } impl_scan!(i16, i32, i64, isize, u16, u32, u64, usize, String); pub enum Bytes {} impl Scan for Bytes { type Output = &'static [u8]; fn scan(s: &mut IO) -> Self::Output { s.scan_str().as_bytes() } } pub enum Chars {} impl Scan for Chars { type Output = Vec<char>; fn scan(s: &mut IO) -> Self::Output { s.scan_str().chars().collect() } } pub enum Usize1 {} impl Scan for Usize1 { type Output = usize; fn scan(s: &mut IO) -> Self::Output { s.scan::<usize>().wrapping_sub(1) } } impl<T: Scan, U: Scan> Scan for (T, U) { type Output = (T::Output, U::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s)) } } impl<T: Scan, U: Scan, V: Scan> Scan for (T, U, V) { type Output = (T::Output, U::Output, V::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s)) } } impl<T: Scan, U: Scan, V: Scan, W: Scan> Scan for (T, U, V, W) { type Output = (T::Output, U::Output, V::Output, W::Output); fn scan(s: &mut IO) -> Self::Output { (T::scan(s), U::scan(s), V::scan(s), W::scan(s)) } } pub trait Print { fn print(w: &mut IO, x: Self); } macro_rules! impl_print_int { ($($t:ty),*) => { $( impl Print for $t { fn print(w: &mut IO, x: Self) { w.buf.write_all(x.to_string().as_bytes()).unwrap(); } } )* }; } impl_print_int!(i16, i32, i64, isize, u16, u32, u64, usize); impl Print for u8 { fn print(w: &mut IO, x: Self) { w.buf.write_all(&[x]).unwrap(); } } impl Print for &[u8] { fn print(w: &mut IO, x: Self) { w.buf.write_all(x).unwrap(); } } impl Print for &str { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl Print for String { fn print(w: &mut IO, x: Self) { w.print(x.as_bytes()); } } impl<T: Print, U: Print> Print for (T, U) { fn print(w: &mut IO, (x, y): Self) { w.print(x); w.print(" "); w.print(y); } } impl<T: Print, U: Print, V: Print> Print for (T, U, V) { fn print(w: &mut IO, (x, y, z): Self) { w.print(x); w.print(" "); w.print(y); w.print(" "); w.print(z); } } mod neboccoio_macro { #[macro_export] macro_rules! input { (@start $io:tt @read @rest) => {}; (@start $io:tt @read @rest, $($rest: tt)*) => { input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @rest mut $($rest:tt)*) => { input!(@start $io @read @mut [mut] @rest $($rest)*) }; (@start $io:tt @read @rest $($rest:tt)*) => { input!(@start $io @read @mut [] @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: [$kind:tt; $len:expr] $($rest:tt)*) => { let $($mut)* $var = $io.scan_vec::<$kind>($len); input!(@start $io @read @rest $($rest)*) }; (@start $io:tt @read @mut [$($mut:tt)?] @rest $var:tt: $kind:tt $($rest:tt)*) => { let $($mut)* $var = $io.scan::<$kind>(); input!(@start $io @read @rest $($rest)*) }; (from $io:tt $($rest:tt)*) => { input!(@start $io @read @rest $($rest)*) }; } } // ------------ io module end ------------