#1167388 (Rust) No.3557 KCPC or KUPC 2

• 問題: No.3557 KCPC or KUPC 2
• ユーザー: akkey
• 提出日時: 2026-05-29 19:57:30
• 言語: Rust (1.94.0 + proconio + num + itertools)
• 結果: WA
• 実行時間: -
• コード長: 18,384 bytes
• コンパイル時間: 3,716 ms
• コンパイル使用メモリ: 204,540 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2026-05-29 19:57:45
• 合計ジャッジ時間: 3,848 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge4_0

サブタスク	配点	結果
部分点1	10 %	AC * 18 WA * 11 RE * 1
部分点2	40 %	AC * 18 WA * 12
部分点3	50 %	AC * 16 WA * 14
合計	0 点

ソースコード

#![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: i128,
        mut a: i128, b: i128, c: i128,
        mut d: i128, e: i128, f: i128
    }
    let k0 = partition_point(0, (n - a) / c, |r| (a * r + r * (r - 1) / 2) * b <= n) - 1;
    let c0 = k0 * b + (n - (a * k0 + k0 * (k0 - 1) / 2) * b) / (a + b * k0);

    let k1 = partition_point(0, (n - d) / f, |r| (d * r + r * (r - 1) / 2) * e <= n) - 1;
    let c1 = k1 * e + (n - (d * k1 + k1 * (k1 - 1) / 2) * e) / (d + e * k1);
    debug!(k0, k1, c0, c1);
    if c0 == c1 {
        println!("Same");
    } else if c0 < c1 {
        println!("KCPC");
    } else {
        println!("KUPC");
    }
}

#[allow(unused)]
fn partition_point<I: num::Integer + Copy>(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 <int n> 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 <int m> 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<u64>,
        mut m: W<u64>,
        mut a: W<u64>,
        mut b: W<u64>,
    ) -> W<u64> {
        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
    }
}