#![allow(non_snake_case, unused_imports, unused_macros)] use itertools::Itertools; use proconio::{fastout, input, marker::Usize1}; macro_rules! debug { ($($a:expr),* $(,)*) => { #[cfg(debug_assertions)] eprintln!(concat!($("| ", stringify!($a), "={:?} "),*, "|"), $(&$a),*); }; } macro_rules! ndvec { ($v:expr; $n:expr) => { vec![$v; $n] }; ($v:expr; $n:expr, $($ns:expr),+) => { vec![ndvec![$v; $($ns),+]; $n] }; } macro_rules! yes_no { ($e:expr) => { if $e { println!("Yes"); } else { println!("No"); } }; } #[fastout] fn main() { input! { n: i64, mut a: i64, b: i64, c: i64, mut d: i64, e: i64, f: i64 } let c0 = partition_point(0, (n - a) / c, |r| a * r + floor_sum(r, b, c, 0) < n); let c1 = partition_point(0, (n - d) / f, |r| d * r + floor_sum(r, e, f, 0) < n); debug!(c0, c1); if c0 == c1 { println!("Same"); } else if c0 < c1 { println!("KCPC"); } else { println!("KUPC"); } } #[allow(unused)] fn partition_point(mut l: I, mut r: I, mut f: impl FnMut(I) -> bool) -> I { let one = I::one(); let two = one + one; while l < r { let p = (r - l) / two + l; if f(p) { l = p + one; } else { r = p; } } l } #[test] fn test_isqrt() { for i in 0..100usize { assert_eq!(i.isqrt(), partition_point(0, i + 1, |k| k * k <= i) - 1); } } #[allow(dead_code)] pub(crate) fn ceil_pow2(n: u32) -> u32 { 32 - n.saturating_sub(1).leading_zeros() } use std::{ cmp::Ordering, fmt, iter::{Product, Sum}, marker::PhantomData, ops::{ Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div, DivAssign, Mul, MulAssign, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub, SubAssign, } }; mod internal_math { // remove this after dependencies has been added #![allow(dead_code)] use std::{mem::swap, num::Wrapping as W}; /// # Arguments /// * `m` `1 <= m` /// /// # Returns /// x mod m /* const */ pub(crate) fn safe_mod(mut x: i64, m: i64) -> i64 { x %= m; if x < 0 { x += m; } x } /// Fast modular by barrett reduction /// Reference: https://en.wikipedia.org/wiki/Barrett_reduction /// NOTE: reconsider after Ice Lake pub(crate) struct Barrett { pub(crate) _m: u32, pub(crate) im: u64, } impl Barrett { /// # Arguments /// * `m` `1 <= m` /// (Note: `m <= 2^31` should also hold, which is undocumented in the original library. /// See the [pull reqeust commment](https://github.com/rust-lang-ja/ac-library-rs/pull/3#discussion_r484661007) /// for more details.) pub(crate) fn new(m: u32) -> Barrett { Barrett { _m: m, im: (-1i64 as u64 / m as u64).wrapping_add(1), } } /// # Returns /// `m` pub(crate) fn umod(&self) -> u32 { self._m } /// # Parameters /// * `a` `0 <= a < m` /// * `b` `0 <= b < m` /// /// # Returns /// a * b % m #[allow(clippy::many_single_char_names)] pub(crate) fn mul(&self, a: u32, b: u32) -> u32 { mul_mod(a, b, self._m, self.im) } } /// Calculates `a * b % m`. /// /// * `a` `0 <= a < m` /// * `b` `0 <= b < m` /// * `m` `1 <= m <= 2^31` /// * `im` = ceil(2^64 / `m`) #[allow(clippy::many_single_char_names)] pub(crate) fn mul_mod(a: u32, b: u32, m: u32, im: u64) -> u32 { // [1] m = 1 // a = b = im = 0, so okay // [2] m >= 2 // im = ceil(2^64 / m) // -> im * m = 2^64 + r (0 <= r < m) // let z = a*b = c*m + d (0 <= c, d < m) // a*b * im = (c*m + d) * im = c*(im*m) + d*im = c*2^64 + c*r + d*im // c*r + d*im < m * m + m * im < m * m + 2^64 + m <= 2^64 + m * (m + 1) < 2^64 * 2 // ((ab * im) >> 64) == c or c + 1 let mut z = a as u64; z *= b as u64; let x = (((z as u128) * (im as u128)) >> 64) as u64; let mut v = z.wrapping_sub(x.wrapping_mul(m as u64)) as u32; if m <= v { v = v.wrapping_add(m); } v } /// # Parameters /// * `n` `0 <= n` /// * `m` `1 <= m` /// /// # Returns /// `(x ** n) % m` /* const */ #[allow(clippy::many_single_char_names)] pub(crate) fn pow_mod(x: i64, mut n: i64, m: i32) -> i64 { if m == 1 { return 0; } let _m = m as u32; let mut r: u64 = 1; let mut y: u64 = safe_mod(x, m as i64) as u64; while n != 0 { if (n & 1) > 0 { r = (r * y) % (_m as u64); } y = (y * y) % (_m as u64); n >>= 1; } r as i64 } /// Reference: /// M. Forisek and J. Jancina, /// Fast Primality Testing for Integers That Fit into a Machine Word /// /// # Parameters /// * `n` `0 <= n` /* const */ pub(crate) fn is_prime(n: i32) -> bool { let n = n as i64; match n { _ if n <= 1 => return false, 2 | 7 | 61 => return true, _ if n % 2 == 0 => return false, _ => {} } let mut d = n - 1; while d % 2 == 0 { d /= 2; } for &a in &[2, 7, 61] { let mut t = d; let mut y = pow_mod(a, t, n as i32); while t != n - 1 && y != 1 && y != n - 1 { y = y * y % n; t <<= 1; } if y != n - 1 && t % 2 == 0 { return false; } } true } // omitted // template constexpr bool is_prime = is_prime_constexpr(n); /// # Parameters /// * `b` `1 <= b` /// /// # Returns /// (g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g /* const */ #[allow(clippy::many_single_char_names)] pub(crate) fn inv_gcd(a: i64, b: i64) -> (i64, i64) { let a = safe_mod(a, b); if a == 0 { return (b, 0); } // Contracts: // [1] s - m0 * a = 0 (mod b) // [2] t - m1 * a = 0 (mod b) // [3] s * |m1| + t * |m0| <= b let mut s = b; let mut t = a; let mut m0 = 0; let mut m1 = 1; while t != 0 { let u = s / t; s -= t * u; m0 -= m1 * u; // |m1 * u| <= |m1| * s <= b // [3]: // (s - t * u) * |m1| + t * |m0 - m1 * u| // <= s * |m1| - t * u * |m1| + t * (|m0| + |m1| * u) // = s * |m1| + t * |m0| <= b swap(&mut s, &mut t); swap(&mut m0, &mut m1); } // by [3]: |m0| <= b/g // by g != b: |m0| < b/g if m0 < 0 { m0 += b / s; } (s, m0) } /// Compile time (currently not) primitive root /// @param m must be prime /// @return primitive root (and minimum in now) /* const */ pub(crate) fn primitive_root(m: i32) -> i32 { match m { 2 => return 1, 167_772_161 => return 3, 469_762_049 => return 3, 754_974_721 => return 11, 998_244_353 => return 3, _ => {} } let mut divs = [0; 20]; divs[0] = 2; let mut cnt = 1; let mut x = (m - 1) / 2; while x % 2 == 0 { x /= 2; } for i in (3..i32::MAX).step_by(2) { if i as i64 * i as i64 > x as i64 { break; } if x % i == 0 { divs[cnt] = i; cnt += 1; while x % i == 0 { x /= i; } } } if x > 1 { divs[cnt] = x; cnt += 1; } let mut g = 2; loop { if (0..cnt).all(|i| pow_mod(g, ((m - 1) / divs[i]) as i64, m) != 1) { break g as i32; } g += 1; } } // omitted // template constexpr int primitive_root = primitive_root_constexpr(m); /// # Arguments /// * `n` `n < 2^32` /// * `m` `1 <= m < 2^32` /// /// # Returns /// `sum_{i=0}^{n-1} floor((ai + b) / m) (mod 2^64)` /* const */ #[allow(clippy::many_single_char_names)] pub(crate) fn floor_sum_unsigned( mut n: W, mut m: W, mut a: W, mut b: W, ) -> W { let mut ans = W(0); loop { if a >= m { if n > W(0) { ans += n * (n - W(1)) / W(2) * (a / m); } a %= m; } if b >= m { ans += n * (b / m); b %= m; } let y_max = a * n + b; if y_max < m { break; } // y_max < m * (n + 1) // floor(y_max / m) <= n n = y_max / m; b = y_max % m; std::mem::swap(&mut m, &mut a); } ans } } use std::mem::swap; /// Returns $x^n \bmod m$. /// /// # Constraints /// /// - $0 \leq n$ /// - $1 \leq m$ /// /// # Panics /// /// Panics if the above constraints are not satisfied. /// /// # Complexity /// /// - $O(\log n)$ /// /// # Example /// /// ``` /// use ac_library::math; /// /// assert_eq!(math::pow_mod(2, 10000, 7), 2); /// ``` #[allow(clippy::many_single_char_names)] pub fn pow_mod(x: i64, mut n: i64, m: u32) -> u32 { assert!(0 <= n && 1 <= m && m <= 2u32.pow(31)); if m == 1 { return 0; } let bt = internal_math::Barrett::new(m); let mut r = 1; let mut y = internal_math::safe_mod(x, m as i64) as u32; while n != 0 { if n & 1 != 0 { r = bt.mul(r, y); } y = bt.mul(y, y); n >>= 1; } r } /// Returns an integer $y \in [0, m)$ such that $xy \equiv 1 \pmod m$. /// /// # Constraints /// /// - $\gcd(x, m) = 1$ /// - $1 \leq m$ /// /// # Panics /// /// Panics if the above constraints are not satisfied. /// /// # Complexity /// /// - $O(\log m)$ /// /// # Example /// /// ``` /// use ac_library::math; /// /// assert_eq!(math::inv_mod(3, 7), 5); /// ``` pub fn inv_mod(x: i64, m: i64) -> i64 { assert!(1 <= m); let z = internal_math::inv_gcd(x, m); assert!(z.0 == 1); z.1 } /// Performs CRT (Chinese Remainder Theorem). /// /// Given two sequences $r, m$ of length $n$, this function solves the modular equation system /// /// \\[ /// x \equiv r_i \pmod{m_i}, \forall i \in \\{0, 1, \cdots, n - 1\\} /// \\] /// /// If there is no solution, it returns $(0, 0)$. /// /// Otherwise, all of the solutions can be written as the form $x \equiv y \pmod z$, using integer $y, z\\ (0 \leq y < z = \text{lcm}(m))$. /// It returns this $(y, z)$. /// /// If $n = 0$, it returns $(0, 1)$. /// /// # Constraints /// /// - $|r| = |m|$ /// - $1 \leq m_{\forall i}$ /// - $\text{lcm}(m)$ is in `i64` /// /// # Panics /// /// Panics if the above constraints are not satisfied. /// /// # Complexity /// /// - $O(n \log \text{lcm}(m))$ /// /// # Example /// /// ``` /// use ac_library::math; /// /// let r = [2, 3, 2]; /// let m = [3, 5, 7]; /// assert_eq!(math::crt(&r, &m), (23, 105)); /// ``` pub fn crt(r: &[i64], m: &[i64]) -> (i64, i64) { assert_eq!(r.len(), m.len()); // Contracts: 0 <= r0 < m0 let (mut r0, mut m0) = (0, 1); for (&(mut ri), &(mut mi)) in r.iter().zip(m.iter()) { assert!(1 <= mi); ri = internal_math::safe_mod(ri, mi); if m0 < mi { swap(&mut r0, &mut ri); swap(&mut m0, &mut mi); } if m0 % mi == 0 { if r0 % mi != ri { return (0, 0); } continue; } // assume: m0 > mi, lcm(m0, mi) >= 2 * max(m0, mi) // (r0, m0), (ri, mi) -> (r2, m2 = lcm(m0, m1)); // r2 % m0 = r0 // r2 % mi = ri // -> (r0 + x*m0) % mi = ri // -> x*u0*g = ri-r0 (mod u1*g) (u0*g = m0, u1*g = mi) // -> x = (ri - r0) / g * inv(u0) (mod u1) // im = inv(u0) (mod u1) (0 <= im < u1) let (g, im) = internal_math::inv_gcd(m0, mi); let u1 = mi / g; // |ri - r0| < (m0 + mi) <= lcm(m0, mi) if (ri - r0) % g != 0 { return (0, 0); } // u1 * u1 <= mi * mi / g / g <= m0 * mi / g = lcm(m0, mi) let x = (ri - r0) / g % u1 * im % u1; // |r0| + |m0 * x| // < m0 + m0 * (u1 - 1) // = m0 + m0 * mi / g - m0 // = lcm(m0, mi) r0 += x * m0; m0 *= u1; // -> lcm(m0, mi) if r0 < 0 { r0 += m0 }; } (r0, m0) } /// Returns /// /// $$\sum_{i = 0}^{n - 1} \left\lfloor \frac{a \times i + b}{m} \right\rfloor.$$ /// /// It returns the answer in $\bmod 2^{\mathrm{64}}$, if overflowed. /// /// # Constraints /// /// - $0 \leq n \lt 2^{32}$ /// - $1 \leq m \lt 2^{32}$ /// /// # Panics /// /// Panics if the above constraints are not satisfied and overflow or division by zero occurred. /// /// # Complexity /// /// - $O(\log{(m+a)})$ /// /// # Example /// /// ``` /// use ac_library::math; /// /// assert_eq!(math::floor_sum(6, 5, 4, 3), 13); /// ``` #[allow(clippy::many_single_char_names)] pub fn floor_sum(n: i64, m: i64, a: i64, b: i64) -> i64 { use std::num::Wrapping as W; assert!((0..1i64 << 32).contains(&n)); assert!((1..1i64 << 32).contains(&m)); let mut ans = W(0_u64); let (wn, wm, mut wa, mut wb) = (W(n as u64), W(m as u64), W(a as u64), W(b as u64)); if a < 0 { let a2 = W(internal_math::safe_mod(a, m) as u64); ans -= wn * (wn - W(1)) / W(2) * ((a2 - wa) / wm); wa = a2; } if b < 0 { let b2 = W(internal_math::safe_mod(b, m) as u64); ans -= wn * ((b2 - wb) / wm); wb = b2; } let ret = ans + internal_math::floor_sum_unsigned(wn, wm, wa, wb); ret.0 as i64 } #[cfg(test)] mod tests { #![allow(clippy::unreadable_literal)] #![allow(clippy::cognitive_complexity)] use super::*; #[test] fn test_pow_mod() { assert_eq!(pow_mod(0, 0, 1), 0); assert_eq!(pow_mod(0, 0, 3), 1); assert_eq!(pow_mod(0, 0, 723), 1); assert_eq!(pow_mod(0, 0, 998244353), 1); assert_eq!(pow_mod(0, 0, 2u32.pow(31)), 1); assert_eq!(pow_mod(0, 1, 1), 0); assert_eq!(pow_mod(0, 1, 3), 0); assert_eq!(pow_mod(0, 1, 723), 0); assert_eq!(pow_mod(0, 1, 998244353), 0); assert_eq!(pow_mod(0, 1, 2u32.pow(31)), 0); assert_eq!(pow_mod(0, i64::MAX, 1), 0); assert_eq!(pow_mod(0, i64::MAX, 3), 0); assert_eq!(pow_mod(0, i64::MAX, 723), 0); assert_eq!(pow_mod(0, i64::MAX, 998244353), 0); assert_eq!(pow_mod(0, i64::MAX, 2u32.pow(31)), 0); assert_eq!(pow_mod(1, 0, 1), 0); assert_eq!(pow_mod(1, 0, 3), 1); assert_eq!(pow_mod(1, 0, 723), 1); assert_eq!(pow_mod(1, 0, 998244353), 1); assert_eq!(pow_mod(1, 0, 2u32.pow(31)), 1); assert_eq!(pow_mod(1, 1, 1), 0); assert_eq!(pow_mod(1, 1, 3), 1); assert_eq!(pow_mod(1, 1, 723), 1); assert_eq!(pow_mod(1, 1, 998244353), 1); assert_eq!(pow_mod(1, 1, 2u32.pow(31)), 1); assert_eq!(pow_mod(1, i64::MAX, 1), 0); assert_eq!(pow_mod(1, i64::MAX, 3), 1); assert_eq!(pow_mod(1, i64::MAX, 723), 1); assert_eq!(pow_mod(1, i64::MAX, 998244353), 1); assert_eq!(pow_mod(1, i64::MAX, 2u32.pow(31)), 1); assert_eq!(pow_mod(i64::MAX, 0, 1), 0); assert_eq!(pow_mod(i64::MAX, 0, 3), 1); assert_eq!(pow_mod(i64::MAX, 0, 723), 1); assert_eq!(pow_mod(i64::MAX, 0, 998244353), 1); assert_eq!(pow_mod(i64::MAX, 0, 2u32.pow(31)), 1); assert_eq!(pow_mod(i64::MAX, i64::MAX, 1), 0); assert_eq!(pow_mod(i64::MAX, i64::MAX, 3), 1); assert_eq!(pow_mod(i64::MAX, i64::MAX, 723), 640); assert_eq!(pow_mod(i64::MAX, i64::MAX, 998244353), 683296792); assert_eq!(pow_mod(i64::MAX, i64::MAX, 2u32.pow(31)), 2147483647); assert_eq!(pow_mod(2, 3, 1_000_000_007), 8); assert_eq!(pow_mod(5, 7, 1_000_000_007), 78125); assert_eq!(pow_mod(123, 456, 1_000_000_007), 565291922); } #[test] #[should_panic] fn test_inv_mod_1() { inv_mod(271828, 0); } #[test] #[should_panic] fn test_inv_mod_2() { inv_mod(3141592, 1000000008); } #[test] fn test_crt() { let a = [44, 23, 13]; let b = [13, 50, 22]; assert_eq!(crt(&a, &b), (1773, 7150)); let a = [12345, 67890, 99999]; let b = [13, 444321, 95318]; assert_eq!(crt(&a, &b), (103333581255, 550573258014)); let a = [0, 3, 4]; let b = [1, 9, 5]; assert_eq!(crt(&a, &b), (39, 45)); } #[test] fn test_floor_sum() { assert_eq!(floor_sum(0, 1, 0, 0), 0); assert_eq!(floor_sum(1_000_000_000, 1, 1, 1), 500_000_000_500_000_000); assert_eq!( floor_sum(1_000_000_000, 1_000_000_000, 999_999_999, 999_999_999), 499_999_999_500_000_000 ); assert_eq!(floor_sum(332955, 5590132, 2231, 999423), 22014575); for n in 0..20 { for m in 1..20 { for a in -20..20 { for b in -20..20 { assert_eq!(floor_sum(n, m, a, b), floor_sum_naive(n, m, a, b)); } } } } } #[allow(clippy::many_single_char_names)] fn floor_sum_naive(n: i64, m: i64, a: i64, b: i64) -> i64 { let mut ans = 0; for i in 0..n { let z = a * i + b; ans += (z - internal_math::safe_mod(z, m)) / m; } ans } }