NZIC 2026 Round 1（新西兰信息学竞赛 2025 第一轮）

C.Betty the Cat 2（猫咪 Betty 2）

输入： 标准输入（stdin） 输出： 标准输出（stdout） 内存限制： 64 MB 时间限制： 1.0 秒

• problem statement
• submit
• submissions

---

题目描述

猫咪 Betty 最近开始去健身房锻炼，并且想让自己的肌肉变得更强壮。

为了帮助自己增肌，她买了两种装有肌酸饼干的盒子：

• 每盒有 (A) 块饼干；
• 每盒有 (B) 块饼干。

这两种盒子她都有无限多个。

当 Betty 打开一盒饼干时，出于道德上的责任，她必须把这一整盒里的所有饼干都吃完。

Betty 每天的目标是吃：

$$K$$

块饼干。

她想知道：

实际吃掉的饼干数量，最多能有多接近目标 (K)？

同时，在达到这个最接近的数量时：

最少需要吃多少盒饼干？

---

注意事项

如果你使用的是对整数类型敏感的语言，例如：

• C
• C++
• C#
• Java

应该使用 64 位整数类型，以避免整数溢出。

例如：

• C / C++：long long
• C# / Java：long

---

输入格式

输入只有一行，包含三个用空格分隔的整数：

A B K

---

输出格式

输出两个用空格分隔的整数：

difference boxes

其中：

• 第一个整数表示实际吃掉的饼干数量与目标 (K) 之间的最小绝对差；
• 第二个整数表示达到这个最小绝对差时，所需要的最少盒子数量。

---

数据范围

对于所有子任务：

$$1\le A,B\le1000$$ $$1\le K\le10^{18}$$

---

子任务

• 子任务 1（+10%）：

$$A=1$$

并且：

$$K\le100000$$

• 子任务 2（+25%）：

$$A=B$$

并且：

$$K\le100000$$

• 子任务 3（+40%）：

$$K\le100000$$

• 子任务 4（+25%）：

没有额外限制。

---

样例说明

样例 1

如果 Betty 吃：

• 2 盒每盒 2 块的饼干；
• 2 盒每盒 3 块的饼干；

那么总共吃：

$$2\times2+2\times3=10$$

块饼干。

正好达到目标：

$$K=10$$

因此与目标的差为：

$$0$$

并且一共使用：

$$2+2=4$$

盒饼干。

而且 4 盒已经是能够达到目标 10 所需的最少盒数。

所以输出：

0 4

---

样例 2

Betty 的目标是：

$$3$$

块饼干。

两种盒子的大小分别为：

$$19$$

和：

$$6$$

无论打开哪一种盒子，都会超过目标很多。

因此最好的选择是：

一盒也不吃。

实际吃掉：

$$0$$

块。

与目标的差为：

$$|0-3|=3$$

需要：

$$0$$

盒。

所以输出：

3 0

---

样例 3

两种盒子的大小都是：

$$8$$

目标为：

$$23$$

如果吃 3 盒：

$$3\times8=24$$

与目标的差：

$$|24-23|=1$$

这是能够达到的最小差值。

因此需要：

$$3$$

盒。

所以输出：

1 3

---

样例输入 1

2 3 10

样例输出 1

0 4

---

样例输入 2

19 6 3

样例输出 2

3 0

---

样例输入 3

8 8 23

样例输出 3

1 3

测试点编号	层级	输入 A B K	标准输出	特殊性质 / 覆盖点
1	弱数据	1 1 1	0 1	最小正整数、A=B、恰好达到目标
2		8 3 14	0 3	A>B，覆盖交换分支；混合两种盒子精确达到目标
3	正常数据	4 10 9	1 1	总数 8 和 10 与目标等距，检验平局时选择盒数更少的方案
4		6 10 15	1 2	gcd(A,B)=2，无法精确达到；最优总数为超过目标的 16
5	极限数据	10¹², 1.5×10¹², 9×10¹⁸−1	1 6000000	接近 long long 上界、大规模盒数、向上取整得到最优解