結果

問題 No.2119 一般化百五減算
ユーザー Moss_Local
提出日時 2022-11-04 22:26:05
言語 Rust
(1.83.0 + proconio)
結果
WA  
実行時間 -
コード長 8,859 bytes
コンパイル時間 13,351 ms
コンパイル使用メモリ 378,912 KB
実行使用メモリ 5,760 KB
最終ジャッジ日時 2024-07-18 20:21:27
合計ジャッジ時間 20,181 ms
ジャッジサーバーID
(参考情報)
judge2 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 24 WA * 1
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unnecessary parentheses around type
  --> src/main.rs:85:15
   |
85 | fn readi() -> (i64) {
   |               ^   ^
   |
   = note: `#[warn(unused_parens)]` on by default
help: remove these parentheses
   |
85 - fn readi() -> (i64) {
85 + fn readi() -> i64 {
   |

warning: unused variable: `i`
   --> src/main.rs:271:9
    |
271 |     for i in 0..m {
    |         ^ help: if this is intentional, prefix it with an underscore: `_i`
    |
    = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:288:9
    |
288 |     let mut y1 = pre_garner(&mut d1, 101737);
    |         ----^^
    |         |
    |         help: remove this `mut`
    |
    = note: `#[warn(unused_mut)]` on by default

warning: variable does not need to be mutable
   --> src/main.rs:300:9
    |
300 |     let mut x1 = garner(d1, 101737);
    |         ----^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:301:9
    |
301 |     let mut x2 = garner(d2, 101741);
    |         ----^^
    |         |
    |         help: remove this `mut`

warning: variable does not need to be mutable
   --> src/main.rs:306:9
    |
306 |     let mut x = x1;
    |         ----^
    |         |
    |         help: remove this `mut`

ソースコード

diff #
プレゼンテーションモードにする

// -*- coding:utf-8-unix -*-
// #![feature(map_first_last)]
#![allow(dead_code)]
#![allow(unused_imports)]
#![allow(unused_macros)]
use core::num;
use std::any::Any;
use std::cmp::Ordering::*;
use std::collections::btree_map::Values;
use std::collections::*;
use std::convert::*;
use std::convert::{From, Into};
use std::error::Error;
use std::f32::consts::E;
use std::fmt::Debug;
use std::fmt::Display;
use std::fs::File;
use std::hash::Hash;
use std::io::prelude::*;
use std::io::*;
use std::iter::Filter;
use std::iter::FromIterator;
use std::marker::Copy;
use std::mem::*;
use std::ops::BitAnd;
use std::ops::Bound::*;
use std::ops::RangeBounds;
use std::ops::{Add, Mul, Neg, Sub};
use std::process;
use std::slice::from_raw_parts;
use std::str;
use std::vec;
const INF: i64 = 1223372036854775807;
const UINF: usize = INF as usize;
const LINF: i64 = 2147483647;
const INF128: i128 = 1223372036854775807000000000000;
const MOD: i64 = 1000000007;
// const MOD: i64 = 998244353;
const UMOD: usize = MOD as usize;
const M_PI: f64 = 3.14159265358979323846;
// const MOD: i64 = INF;
use std::cmp::*;
use std::collections::*;
use std::io::stdin;
use std::io::stdout;
use std::io::Write;
macro_rules! p {
($x:expr) => {
println!("{}", $x);
};
}
macro_rules! d {
($x:expr) => {
println!("{:?}", $x);
};
}
#[allow(unused_macros)]
pub mod macros {
macro_rules! min { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); std::cmp::min($x, y) } }}
macro_rules! max { ($x: expr) => { $x }; ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); std::cmp::max($x, y) } }}
macro_rules! chmin { ($x: expr, $($xs: expr),+) => {{ let y = macros::min!($($xs),+); if $x > y { $x = y; true } else { false } }}}
macro_rules! chmax { ($x: expr, $($xs: expr),+) => {{ let y = macros::max!($($xs),+); if $x < y { $x = y; true } else { false } }}}
macro_rules! multi_vec { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_vec![$element; ($($lens),*)]; $len] );
        ($element: expr; ($len: expr)) => ( vec![$element; $len] ); }
macro_rules! multi_box_array { ($element: expr; ($len: expr, $($lens: expr),*)) => ( vec![macros::multi_box_array![$element; ($($lens),*)]; $len]
        .into_boxed_slice() ); ($element: expr; ($len: expr)) => ( vec![$element; $len].into_boxed_slice() ); }
#[allow(unused_imports)]
pub(super) use {chmax, chmin, max, min, multi_box_array, multi_vec};
}
fn main() {
solve();
}
// use str::Chars;
#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
let mut s = String::new();
std::io::stdin().read_line(&mut s).ok();
s.trim().parse().ok().unwrap()
}
#[allow(dead_code)]
fn readi() -> (i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
iter.next().unwrap().parse::<i64>().unwrap()
}
#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
read::<String>()
.split_whitespace()
.map(|e| e.parse().ok().unwrap())
.collect()
}
#[allow(dead_code)]
fn read_mat<T: std::str::FromStr>(n: u32) -> Vec<Vec<T>> {
(0..n).map(|_| read_vec()).collect()
}
#[allow(dead_code)]
fn readii() -> (i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readiii() -> (i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readuu() -> (usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readff() -> (f64, f64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<f64>().unwrap(),
iter.next().unwrap().parse::<f64>().unwrap(),
)
}
fn readcc() -> (char, char) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<char>().unwrap(),
iter.next().unwrap().parse::<char>().unwrap(),
)
}
fn readuuu() -> (usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
#[allow(dead_code)]
fn readiiii() -> (i64, i64, i64, i64) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
iter.next().unwrap().parse::<i64>().unwrap(),
)
}
#[allow(dead_code)]
fn readuuuu() -> (usize, usize, usize, usize) {
let mut str = String::new();
let _ = stdin().read_line(&mut str).unwrap();
let mut iter = str.split_whitespace();
(
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
iter.next().unwrap().parse::<usize>().unwrap(),
)
}
pub fn gcd(a: i64, b: i64) -> i64 {
if b == 0 {
a
} else {
gcd(b, a % b)
}
}
pub fn extgcd(a: i64, b: i64) -> (i64, i64, i64) {
if b == 0 {
(a, 1, 0)
} else {
let (gcd, x, y) = extgcd(b, a % b);
(gcd, y, x - (a / b) * y)
}
}
pub fn modinv(a: i64, m: i64) -> i64 {
let (_, x, _) = extgcd(a, m);
(m + x % m) % m
}
#[doc = "compute minimum x from a list of x = r[i] (mod m[i]) all m[i] are co-primes and some r[i] should be non-zero."]
pub fn garner(rm: Vec<(i64, i64)>, mo: i64) -> i64 {
let mut rm = rm;
rm.push((0, mo));
let mut coef = vec![1; rm.len()];
let mut constants = vec![0; rm.len()];
for i in 0..rm.len() - 1 {
let v = (rm[i].0 + rm[i].1 - constants[i]) * modinv(coef[i], rm[i].1) % rm[i].1;
for j in i + 1..rm.len() {
constants[j] += coef[j] * v;
constants[j] %= rm[j].1;
coef[j] *= rm[i].1;
coef[j] %= rm[j].1;
}
}
constants[rm.len() - 1]
}
#[doc = "none if there is no such x"]
pub fn pre_garner(rm: &mut Vec<(i64, i64)>, mo: i64) -> Option<i64> {
let n = rm.len();
for i in 0..n {
for j in 0..i {
let g = gcd(rm[i].1, rm[j].1);
if (rm[i].0 - rm[j].0) % g != 0 {
return None;
}
rm[i].1 /= g;
rm[j].1 /= g;
let mut gi = gcd(rm[i].1, g);
let mut gj = g / gi;
loop {
let g = gcd(gi, gj);
gi *= g;
gj /= g;
if g == 1 {
break;
}
}
rm[i].1 *= gi;
rm[j].1 *= gj;
rm[i].0 %= rm[i].1;
rm[j].0 %= rm[j].1;
}
}
let mut lcm = 1;
for i in 0..n {
lcm = lcm * rm[i].1 % mo;
}
Some(lcm)
}
fn solve() {
let n: usize = read();
let m: usize = read();
let mut data = vec![];
let mut bt = BTreeMap::new();
for i in 0..m {
let (b, c) = readii();
let v = (c % b + b) % b;
data.push(((c % b + b) % b, b));
if bt.get(&b) != None && bt[&b] != v {
println!("Nan");
return;
}
bt.insert(b, v);
}
data.sort();
while data.len() > 5000 {
data.pop();
}
let mut d1 = data.clone();
let mut d2 = data.clone();
let mut y1 = pre_garner(&mut d1, 101737);
if y1.is_none() {
p!("NaN");
return;
}
let y2 = pre_garner(&mut d2, 101741);
if y2.is_none() {
p!("NaN");
return;
}
// x
let mut x1 = garner(d1, 101737);
let mut x2 = garner(d2, 101741);
if x1 != x2 {
p!("NaN");
return;
}
let mut x = x1;
if x > n as i64 {
p!("NaN");
return;
}
p!(x);
// d!(x);
return;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0