結果
| 問題 | No.3557 KCPC or KUPC 2 |
| コンテスト | |
| ユーザー |
 akkey
|
| 提出日時 | 2026-05-29 19:58:51 |
| 言語 | Rust (1.94.0 + proconio + num + itertools) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 18,384 bytes |
| 記録 | |
| コンパイル時間 | 3,839 ms |
| コンパイル使用メモリ | 202,956 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-05-29 19:59:06 |
| 合計ジャッジ時間 | 4,694 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge4_0 |
（要ログイン）
| サブタスク | 配点 | 結果 |
|---|---|---|
| 部分点1 | 10 % | AC * 13 WA * 15 RE * 2 |
| 部分点2 | 40 % | AC * 19 WA * 11 |
| 部分点3 | 50 % | AC * 17 WA * 13 |
| 合計 | 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 + c * 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 + f * 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
}
}