結果
| 問題 | No.2526 Kth Not-divisible Number |
| ユーザー |
 cotton_fn_
|
| 提出日時 | 2023-11-04 20:46:06 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 267 ms / 2,000 ms |
| コード長 | 22,606 bytes |
| コンパイル時間 | 12,993 ms |
| コンパイル使用メモリ | 386,472 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-25 22:19:47 |
| 合計ジャッジ時間 | 16,519 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,812 KB |
| testcase_01 | AC | 1 ms
6,816 KB |
| testcase_02 | AC | 1 ms
6,816 KB |
| testcase_03 | AC | 255 ms
6,944 KB |
| testcase_04 | AC | 254 ms
6,940 KB |
| testcase_05 | AC | 254 ms
6,944 KB |
| testcase_06 | AC | 254 ms
6,940 KB |
| testcase_07 | AC | 255 ms
6,944 KB |
| testcase_08 | AC | 254 ms
6,940 KB |
| testcase_09 | AC | 221 ms
6,940 KB |
| testcase_10 | AC | 267 ms
6,940 KB |
| testcase_11 | AC | 29 ms
6,940 KB |
コンパイルメッセージ
warning: a method with this name may be added to the standard library in the future
--> src/main.rs:183:36
|
183 | (self as $uty).isqrt() as Self
| ^^^^^
...
195 | int!(isize, usize);
| ------------------ in this macro invocation
|
= warning: once this associated item is added to the standard library, the ambiguity may cause an error or change in behavior!
= note: for more information, see issue #48919 <https://github.com/rust-lang/rust/issues/48919>
= help: call with fully qualified syntax `int::UInt::isqrt(...)` to keep using the current method
= note: `#[warn(unstable_name_collisions)]` on by default
= note: this warning originates in the macro `int` (in Nightly builds, run with -Z macro-backtrace for more info)
warning: a method with this name may be added to the standard library in the future
--> src/main.rs:183:36
|
183 | (self as $uty).isqrt() as Self
| ^^^^^
...
196 | int!(i8, u8);
| ------------ in this macro invocation
|
= warning: once this associated item is added to the standard library, the ambiguity may cause an error or change in behavior!
= note: for more information, see issue #48919 <https://github.com/rust-lang/rust/issues/48919>
= help: call with fully qualified syntax `int::UInt::isqrt(...)` to keep using the current method
= note: this warning originates in the macro `int` (in Nightly builds, run with -Z macro-backtrace for more info)
warning: a method with this name may be added to the standard library in the future
--> src/main.rs:183:36
|
183 | (self as $uty).isqrt() as Self
| ^^^^^
...
197 | int!(i16, u16);
| -------------- in this macro invocation
|
= warning: once this associated item is added to the standard library, the ambiguity may cause an error or c
ソースコード
#![allow(unused_imports)]
use input2::*;
use std::{
collections::*,
io::{self, BufWriter, Read, Write},
};
fn run<I: Read, O: Write>(mut ss: Input<I>, mut out: O) {
let t: u32 = ss.input();
for _ in 0..t {
case(&mut ss, &mut out);
}
}
fn case<I: Read, O: Write>(ss: &mut Input<I>, mut out: O) {
use int::*;
let (a, b, k): (i64, i64, i64) = ss.input();
let l = a.lcm(b);
let mut lo = 0;
let mut hi = 4 * k;
while hi - lo > 1 {
let x = lo + (hi - lo) / 2;
let t = x - x / a - x / b + x / l;
if t >= k {
hi = x;
} else {
lo = x;
}
}
wln!(out, "{hi}")
}
fn main() {
let stdin = io::stdin();
let ss = Input::new(stdin.lock());
let stdout = io::stdout();
let out = BufWriter::new(stdout.lock());
run(ss, out);
}
pub mod int {
use std::ops::*;
pub trait UInt:
Sized
+ Copy
+ Eq
+ Ord
+ Add<Output = Self>
+ Sub<Output = Self>
+ Mul<Output = Self>
+ Div<Output = Self>
+ Rem<Output = Self>
{
fn zero() -> Self;
fn one() -> Self;
fn div_floor(self, other: Self) -> Self;
fn div_ceil(self, other: Self) -> Self;
fn abs(self) -> Self;
fn gcd(self, other: Self) -> Self;
fn lcm(self, other: Self) -> Self {
self / self.gcd(other) * other
}
fn isqrt(self) -> Self;
}
pub trait Int: UInt + Neg<Output = Self> {
fn ext_gcd(mut self, mut other: Self) -> (Self, Self, Self) {
use std::mem::swap;
let mut a = (Self::one(), Self::zero());
let mut b = (Self::zero(), Self::one());
while other != Self::zero() {
let d = self / other;
self = self % other;
swap(&mut self, &mut other);
a.0 = a.0 - d * b.0;
a.1 = a.1 - d * b.1;
swap(&mut a, &mut b);
}
if self >= Self::zero() {
(self, a.0, a.1)
} else {
(-self, -a.0, -a.1)
}
}
}
pub fn crt<T: Int>(r1: T, m1: T, r2: T, m2: T) -> Option<(T, T)> {
if m1 > m2 {
return crt(r2, m2, r1, m1);
}
let (g, v1, _) = m1.ext_gcd(m2);
if m1 == g {
return if r1 == r2 % m1 { Some((r1, m1)) } else { None };
}
if (r2 - r1) % g != T::zero() {
return None;
}
let u2 = m2 / g;
let q = (r2 - r1) / g * v1 % u2;
let q = if q >= T::zero() { q } else { u2 + q };
let x = m1 * q + r1;
Some((x, m1 * u2))
}
macro_rules! common_fns {
($ ty : ty) => {
fn zero() -> Self {
0
}
fn one() -> Self {
1
}
fn gcd(self, other: Self) -> Self {
let x = self.abs();
let y = other.abs();
if x == 0 {
return y;
}
if y == 0 {
return x;
}
let tzx = x.trailing_zeros();
let tzy = y.trailing_zeros();
let tzg = tzx.min(tzy);
let mut x = x >> tzx;
let mut y = y >> tzy;
while x != y {
if x > y {
x -= y;
x >>= x.trailing_zeros();
} else {
y -= x;
y >>= y.trailing_zeros();
}
}
x << tzg
}
};
}
macro_rules! uint {
($ ty : ty) => {
impl UInt for $ty {
common_fns!($ty);
fn abs(self) -> Self {
self
}
fn div_floor(self, other: Self) -> Self {
self / other
}
fn div_ceil(self, other: Self) -> Self {
let q = self / other;
let r = self % other;
q + (r != 0) as Self
}
fn isqrt(self) -> Self {
let mut res = 0;
let mut diff = self;
for exp in (0..=(Self::BITS - self.leading_zeros()) / 2).rev() {
if let Some(new_diff) =
diff.checked_sub((res << (exp + 1)) + (1 << (2 * exp)))
{
diff = new_diff;
res += 1 << exp;
}
}
res
}
}
};
}
macro_rules! int {
($ ty : ty , $ uty : ty) => {
impl UInt for $ty {
common_fns!($ty);
fn abs(self) -> Self {
self.abs()
}
fn div_floor(self, other: Self) -> Self {
let q = self / other;
let r = self % other;
q - ((other ^ r < 0) as Self & (r != 0) as Self)
}
fn div_ceil(self, other: Self) -> Self {
let q = self / other;
let r = self % other;
q + ((other ^ r > 0) as Self & (r != 0) as Self)
}
fn isqrt(self) -> Self {
assert!(self >= 0, "the value is negative ({self})");
(self as $uty).isqrt() as Self
}
}
impl Int for $ty {}
};
}
uint!(usize);
uint!(u8);
uint!(u16);
uint!(u32);
uint!(u64);
uint!(u128);
int!(isize, usize);
int!(i8, u8);
int!(i16, u16);
int!(i32, u32);
int!(i64, u64);
int!(i128, u128);
pub fn gcd<T: UInt>(x: T, y: T) -> T {
x.gcd(y)
}
pub fn ext_gcd<T: Int>(x: T, y: T) -> (T, T, T) {
x.ext_gcd(y)
}
pub fn lcm<T: UInt>(x: T, y: T) -> T {
x.lcm(y)
}
}
pub mod input2 {
use std::{
convert::TryInto,
io::{self, Read},
marker::PhantomData,
mem::{self, MaybeUninit},
ptr, slice,
};
pub struct Input<R: ?Sized> {
buf: Vec<u8>,
pos: usize,
len: usize,
src: R,
}
macro_rules! def_input {
($ ty : ident) => {
pub fn $ty(&mut self) -> $ty {
self.input()
}
};
}
impl<R: Read> Input<R> {
pub fn new(src: R) -> Self {
Self::with_capacity(src, 1 << 20)
}
pub fn with_capacity(src: R, cap: usize) -> Self {
Self {
src,
buf: vec![0; cap],
pos: 0,
len: 0,
}
}
pub fn input<T: Parse>(&mut self) -> T {
T::parse(self)
}
pub fn seq<T: Parse>(&mut self, n: usize) -> Seq<T, R> {
Seq {
src: self,
n,
marker: PhantomData,
}
}
pub fn vec<T: Parse>(&mut self, n: usize) -> Vec<T> {
self.seq(n).collect()
}
pub fn str(&mut self) -> &str {
std::str::from_utf8(self.bytes()).expect("utf8 error")
}
pub fn bytes(&mut self) -> &[u8] {
let range = self.bytes_inner();
unsafe { self.buf.get_unchecked(range) }
}
pub fn bytes_vec(&mut self) -> Vec<u8> {
let range = self.bytes_inner();
if range.start == 0 && 2 * range.end >= self.buf.len() {
let buf_len = self.buf.len();
let mut new_buf = vec![0; buf_len];
new_buf[..self.len].copy_from_slice(self.remaining());
let mut res = mem::replace(&mut self.buf, new_buf);
self.pos = 0;
res.truncate(range.end);
res
} else {
self.buf[range].to_vec()
}
}
#[inline]
fn bytes_inner(&mut self) -> std::ops::Range<usize> {
let mut i = 0;
loop {
if self.len > 0 {
if let Some(d) = find_ws(unsafe {
self.buf.get_unchecked(self.pos + i..self.pos + self.len)
}) {
let del = i + d;
let range = self.pos..self.pos + del;
self.pos += del + 1;
self.len -= del + 1;
if del == 0 {
continue;
}
return range;
}
i = self.len;
}
if self.read() == 0 {
let range = self.pos..self.pos + self.len;
self.pos = 0;
self.len = 0;
return range;
}
}
}
#[cold]
fn read(&mut self) -> usize {
if self.pos != 0 {
self.buf.copy_within(self.pos..self.pos + self.len, 0);
self.pos = 0;
}
if self.len == self.buf.len() {
self.buf.resize((2 * self.buf.len()).max(1 << 13), 0);
}
loop {
match self
.src
.read(unsafe { self.buf.get_unchecked_mut(self.len..) })
{
Ok(n) => {
self.len += n;
return n;
}
Err(e) if e.kind() == io::ErrorKind::WouldBlock => {}
Err(e) => panic!("io error: {}", e),
}
}
}
#[inline]
fn remaining(&self) -> &[u8] {
unsafe { self.buf.get_unchecked(self.pos..self.pos + self.len) }
}
def_input!(usize);
def_input!(u8);
def_input!(u16);
def_input!(u32);
def_input!(u64);
def_input!(isize);
def_input!(i8);
def_input!(i16);
def_input!(i32);
def_input!(i64);
def_input!(f32);
def_input!(f64);
}
#[inline]
pub(crate) fn find_ws_naive(s: &[u8]) -> Option<usize> {
for (i, c) in s.iter().enumerate() {
if *c <= b' ' {
return Some(i);
}
}
None
}
const CHUNK_SIZE: usize = mem::size_of::<usize>();
#[inline]
pub(crate) fn find_ws(s: &[u8]) -> Option<usize> {
let offset = (32 + s.as_ptr().align_offset(CHUNK_SIZE)).min(s.len());
let mut i = 0;
while i < offset {
if s[i] <= b' ' {
return Some(i);
}
i += 1;
}
if i < s.len() {
find_ws_long(s, i)
} else {
None
}
}
fn find_ws_long(s: &[u8], mut i: usize) -> Option<usize> {
while i + CHUNK_SIZE <= s.len() {
if let Some(j) = find_ws_usize(usize::from_le_bytes(
unsafe { s.get_unchecked(i..i + CHUNK_SIZE) }
.try_into()
.unwrap(),
)) {
return Some(i + j);
}
i += CHUNK_SIZE;
}
while i < s.len() {
if s[i] <= b' ' {
return Some(i);
}
i += 1;
}
None
}
#[inline]
fn find_ws_usize(s: usize) -> Option<usize> {
const SUB: usize = 0x2121212121212121;
const MASK: usize = 0x8080808080808080;
let t = s.wrapping_sub(SUB) & MASK;
(t != 0).then(|| (t.trailing_zeros() / 8) as usize)
}
pub struct Seq<'a, T, R> {
src: &'a mut Input<R>,
n: usize,
marker: PhantomData<*const T>,
}
impl<'a, T: Parse, R: Read> Iterator for Seq<'a, T, R> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
if self.n > 0 {
self.n -= 1;
Some(self.src.input())
} else {
None
}
}
fn size_hint(&self) -> (usize, Option<usize>) {
(self.n, Some(self.n))
}
}
impl<'a, T: Parse, R: Read> ExactSizeIterator for Seq<'a, T, R> {
fn len(&self) -> usize {
self.size_hint().0
}
}
pub trait Parse {
fn parse<T: Read>(src: &mut Input<T>) -> Self;
}
impl Parse for Vec<u8> {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
src.bytes_vec()
}
}
impl Parse for String {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
String::from_utf8(src.bytes_vec()).unwrap()
}
}
pub trait ParseBytes {
fn parse_bytes(s: &[u8]) -> Self;
}
macro_rules! parse_int {
($ ty : ident , $ ity : ident) => {
impl ParseBytes for $ty {
fn parse_bytes(s: &[u8]) -> Self {
$ty(s, 0)
}
}
impl ParseBytes for $ity {
fn parse_bytes(s: &[u8]) -> Self {
let (minus, s) = if let Some((b'-', s)) = s.split_first() {
(true, s)
} else {
(false, s)
};
let x = $ty(s, 0);
(if minus { (!x).wrapping_add(1) } else { x }) as $ity
}
}
};
}
parse_int!(usize, isize);
parse_int!(u8, i8);
parse_int!(u16, i16);
parse_int!(u32, i32);
parse_int!(u64, i64);
macro_rules! parse {
($ ty : ident) => {
impl Parse for $ty {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
Self::parse_bytes(src.bytes())
}
}
};
}
parse!(usize);
parse!(u8);
parse!(u16);
parse!(u32);
parse!(u64);
parse!(isize);
parse!(i8);
parse!(i16);
parse!(i32);
parse!(i64);
parse!(f32);
parse!(f64);
macro_rules ! tuple { ($ ($ T : ident) ,+) => { impl <$ ($ T : Parse) ,+> Parse for ($ ($ T ,) +) { fn parse < T : Read > (src : & mut Input < T >) -> Self { ($ ($ T :: parse (src) ,) +) } } } ; }
tuple!(A);
tuple!(A, B);
tuple!(A, B, C);
tuple!(A, B, C, D);
tuple!(A, B, C, D, E);
tuple!(A, B, C, D, E, F);
tuple!(A, B, C, D, E, F, G);
tuple!(A, B, C, D, E, F, G, H);
impl<T: Parse, const N: usize> Parse for [T; N] {
fn parse<R: Read>(src: &mut Input<R>) -> Self {
struct Guard<T> {
ptr: *mut T,
i: usize,
}
impl<T> Drop for Guard<T> {
fn drop(&mut self) {
unsafe {
ptr::drop_in_place(slice::from_raw_parts_mut(self.ptr, self.i));
}
}
}
let mut res: MaybeUninit<[T; N]> = MaybeUninit::uninit();
let mut g = Guard {
ptr: res.as_mut_ptr() as *mut T,
i: 0,
};
unsafe {
while g.i < N {
g.ptr.add(g.i).write(src.input());
g.i += 1;
}
mem::forget(g);
res.assume_init()
}
}
}
#[inline]
fn toi8bytes(s: &[u8]) -> (u32, &[u8]) {
let (p, rest) = s.split_at(8);
let x = u64::from_le_bytes(p.try_into().unwrap());
const MASK1: u64 = 0x000f000f000f000f;
let hi = (x >> 8) & MASK1;
let lo = x & MASK1;
let x = 10 * lo + hi;
const MASK2: u64 = 0x0000ffff0000ffff;
let hi = (x >> 16) & MASK2;
let lo = x & MASK2;
let x = 100 * lo + hi;
let hi = (x >> 32) as u32;
let lo = x as u32;
let x = 10000 * lo + hi;
(x, rest)
}
#[inline]
fn toi4bytes(s: &[u8]) -> (u32, &[u8]) {
let (p, rest) = s.split_at(4);
let x = u32::from_le_bytes(p.try_into().unwrap());
const MASK: u32 = 0x000f000f;
let hi = (x >> 8) & MASK;
let lo = x & MASK;
let x = 10 * lo + hi;
let hi = x >> 16;
let lo = x & 0x0000ffff;
let x = 100 * lo + hi;
(x, rest)
}
#[cfg(target_pointer_width = "32")]
fn usize(s: &[u8], pre: usize) -> usize {
u32(s, pre as u32) as usize
}
#[cfg(target_pointer_width = "64")]
fn usize(s: &[u8], pre: usize) -> usize {
u64(s, pre as u64) as usize
}
#[inline]
fn u64(mut s: &[u8], pre: u64) -> u64 {
let mut res = pre;
while s.len() >= 8 {
let (x, rest) = toi8bytes(s);
res = 100000000 * res + x as u64;
s = rest;
}
if s.len() >= 4 {
let (x, rest) = toi4bytes(s);
res = 10000 * res + x as u64;
s = rest;
}
for &c in s {
res = 10 * res + (c & 0xf) as u64;
}
res
}
#[inline]
fn u32(mut s: &[u8], pre: u32) -> u32 {
let mut res = pre;
if s.len() >= 8 {
let (x, rest) = toi8bytes(s);
res = x;
s = rest;
}
if s.len() >= 4 {
let (x, rest) = toi4bytes(s);
res = 10000 * res + x;
s = rest;
}
for &c in s {
res = 10 * res + (c & 0xf) as u32;
}
res
}
#[inline]
fn u16(mut s: &[u8], pre: u16) -> u16 {
let mut res = pre;
if s.len() >= 4 {
let (x, rest) = toi4bytes(s);
res = 10000 * res + x as u16;
s = rest;
}
for &c in s {
res = 10 * res + (c & 0xf) as u16;
}
res
}
#[inline]
fn u8(s: &[u8], pre: u8) -> u8 {
let mut res = pre;
for &c in s {
res = 10 * res + (c & 0xf);
}
res
}
macro_rules! float {
($ ty : ident , $ uty : ident) => {
impl ParseBytes for $ty {
fn parse_bytes(s: &[u8]) -> Self {
const TEN: [$ty; 18] = [
1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10, 1e11, 1e12, 1e13,
1e14, 1e15, 1e16, 1e17,
];
let (minus, s) = if let Some((b'-', s)) = s.split_first() {
(true, s)
} else {
(false, s)
};
let (int, fract) = if let Some(p) = s.iter().position(|c| *c == b'.') {
(&s[..p], &s[p + 1..])
} else {
(s, &s[..0])
};
let x = $uty(int, 0);
let x = if fract.is_empty() {
x as $ty
} else {
let ten = TEN
.get(fract.len())
.copied()
.unwrap_or_else(|| $ty::powi(10.0, fract.len() as _));
$uty(fract, x) as $ty / ten
};
if minus {
-x
} else {
x
}
}
}
};
}
float!(f32, u32);
float!(f64, u64);
impl Parse for char {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
let s = src.str();
let mut cs = s.chars();
match cs.next() {
Some(c) if cs.as_str().is_empty() => c,
_ => panic!("input is not single char"),
}
}
}
pub struct Byte(pub u8);
impl Parse for Byte {
fn parse<T: Read>(src: &mut Input<T>) -> Self {
if let [b] = src.bytes() {
Byte(*b)
} else {
panic!("input is not single byte")
}
}
}
}
pub mod macros {
extern "C" {
pub fn isatty(fd: i32) -> i32;
}
#[macro_export]
macro_rules ! w { ($ dst : expr , $ ($ arg : tt) *) => { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0 { write ! ($ dst , "\x1B[1;33m") . unwrap () ; write ! ($ dst , $ ($ arg) *) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ; } else { write ! ($ dst , $ ($ arg) *) . unwrap () ; } } }
#[macro_export]
macro_rules ! wln { ($ dst : expr $ (, $ ($ arg : tt) *) ?) => { { if cfg ! (debug_assertions) && unsafe { $ crate :: macros :: isatty (1) } != 0 { write ! ($ dst , "\x1B[1;33m") . unwrap () ; writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; write ! ($ dst , "\x1B[0m") . unwrap () ; } else { writeln ! ($ dst $ (, $ ($ arg) *) ?) . unwrap () ; } # [cfg (debug_assertions)] $ dst . flush () . unwrap () ; } } }
#[macro_export]
macro_rules! w_iter {
($ dst : expr , $ fmt : expr , $ iter : expr , $ delim : expr) => {{
let mut first = true;
for elem in $iter {
if first {
w!($dst, $fmt, elem);
first = false;
} else {
w!($dst, concat!($delim, $fmt), elem);
}
}
}};
($ dst : expr , $ fmt : expr , $ iter : expr) => {
w_iter!($dst, $fmt, $iter, " ")
};
}
#[macro_export]
macro_rules ! w_iter_ln { ($ dst : expr , $ ($ t : tt) *) => { { w_iter ! ($ dst , $ ($ t) *) ; wln ! ($ dst) ; } } }
#[macro_export]
macro_rules ! e { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprint ! ($ ($ t) *) } }
#[macro_export]
macro_rules ! eln { ($ ($ t : tt) *) => { # [cfg (debug_assertions)] eprintln ! ($ ($ t) *) } }
#[macro_export]
#[doc(hidden)]
macro_rules ! __tstr { ($ h : expr $ (, $ t : expr) +) => { concat ! (__tstr ! ($ ($ t) ,+) , ", " , __tstr ! (@)) } ; ($ h : expr) => { concat ! (__tstr ! () , " " , __tstr ! (@)) } ; () => { "\x1B[94m[{}:{}]\x1B[0m" } ; (@) => { "\x1B[1;92m{}\x1B[0m = {:?}" } }
#[macro_export]
macro_rules ! d { ($ ($ a : expr) ,*) => { if std :: env :: var ("ND") . map (| v | & v == "0") . unwrap_or (true) { eln ! (__tstr ! ($ ($ a) ,*) , file ! () , line ! () , $ (stringify ! ($ a) , $ a) ,*) ; } } ; }
}