The problem

Find three non-negative integers $x$, $y$ and $z$ that meet the following conditions:
\begin{cases}
wx + dy = p, \\
x + y + z = n.
\end{cases}

Constraints

• $1 \le n \le 10^{12}$
• $0 \le p \le 10^{17}$
• $1 \le d < w \le 10^{5}$

分析

先考虑不定方程 $wx + dy = p$，容易排除无解的情形。
令 $W = w / \gcd(w, d),\ D = d / \gcd(w, d),\ M = p / \gcd(w, d)$。
求出 $wx + dy = \gcd(w, d)$ 的一组特解 $x_0, y_0$，通解可表为
$$
\begin{cases}
x = Mx_0 + Dk, \\
y = My_0 - Wk,
\end{cases}
\quad k \in \mathbb{Z}.
$$
至此，问题归结为解不等式
$$
\begin{cases}
x \ge 0 \\
y \ge 0 \\
x + y \le n
\end{cases}
\implies
\begin{cases}
Mx_0 + Dk \ge 0 \\
My_0 -Wk \ge 0 \\
M(x_0 + y_0) - (W-D)k \le n
\end{cases}
\implies
\begin{cases}
k \ge -\frac{Mx_0}{D} \\
k \le \frac{My_0}{W} \\
k \ge \frac{M(x_0 + y_0) - n}{W - D}
\end{cases}
$$

首先要考虑的问题是

计算 $x_0, y_0$ 的过程中会不会暴 long long？

若 $a, b$ 是正整数，对于不定方程 $ax + by = \gcd(a, b)$，设扩展欧几里得算法给出特解 $x_0, y_0$，可以证明：

• 计算过程中所有变量的绝对值都不超过 $\max(a, b)$。
• $|x_0| \le b$，$|y_0| \le a$。

但是 $Mx_0$ 或 $My_0$ 有可能暴 long long。

比赛时，我就卡在这个地方了。实际上道题不必按照解不等式的路子死算。

原问题可以重新表述为：已知 $1 \le d < w \le 10^{5}$，未知数 $x, y$ 是非负整数且满足 $wx + dy = p$，求 $x + y$ 的最小值。把原来的不等式问题转化成求最值问题。
这里的 crucial observation 在于，当 $x + y$ 取到最小值时必有 $y < w$，若不然则 $x +d$ 和 $y - w$ 也满足条件而和更小。因此可以枚举 $y$ 的值。这种做法就不存在计算过程暴long long的问题。

CF1244C The Football Season

原文：https://www.cnblogs.com/Patt/p/11834285.html