use std::io::Write; fn main() { let mut output = std::io::BufWriter::new(std::io::stdout()); input!{ a: [(i64, i64); 3] } let (mut r, mut m) = (Vec::with_capacity(3), Vec::with_capacity(3)); for (ri, mi) in a { r.push(ri); m.push(mi); } let ans = crt(&r, &m).0; writeln!(output, "{}", if ans == 0 {-1} else {ans}).unwrap(); } pub fn crt(r: &[i64], m: &[i64]) -> (i64, i64) { assert_eq!(r.len(), m.len()); let (mut r0, mut m0) = (0, 1); for (&(mut ri), &(mut mi)) in r.iter().zip(m.iter()) { assert!(1 <= mi); ri = ri % mi; if ri < 0 {ri += mi;} if m0 < mi { std::mem::swap(&mut r0, &mut ri); std::mem::swap(&mut m0, &mut mi); } if m0 % mi == 0 { if r0 % mi != ri { return (0, 0); } continue; } let (g, im) = mod_inv(m0, mi); let u1 = mi / g; if (ri - r0) % g != 0 { return (0, 0); } let x = (ri - r0) / g % u1 * im % u1; r0 += x * m0; m0 *= u1; if r0 < 0 { r0 += m0 }; } (r0, m0) } #[inline] pub fn exgcd(a: i64, b: i64, x: &mut i64, y: &mut i64) -> i64 { let mut d = a; if b != 0 { d = exgcd(b, a%b, y, x); *y -= a / b * *x; } else { *x = 1; *y = 0; } d } // ax ≡ g (mod m) // (g, x) #[inline] pub fn mod_inv(a: i64, m: i64) -> (i64, i64) { let mut x = 1; let mut y = 0; (exgcd(a, m, &mut x, &mut y), (m + x % m) % m) } #[allow(dead_code)] mod procon_io { #[macro_export] macro_rules! input { (iter = $iter:expr, $($r:tt)*) => { input_inner!{$iter, $($r)*} }; (buf = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } #[macro_export] macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read!($iter, $t); input_inner!{$iter $($r)*} }; ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => { let mut $var = read!($iter, $t); input_inner!{$iter $($r)*} }; } #[macro_export] macro_rules! read { ($iter:expr, ( $($t:tt),* )) => { ( $(read!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } }