「EZEC-7」Erinnerung

题目描述

小 Y 和小 Z 都是生活在 Arcaea Offline 的精灵。小 Y 有无数片落叶，其中第 $i$ 片落叶的价值为 $C_i$。小 Z 有无数片雪花，其中第 $i$ 片雪花的价值为 $E_i$。经过小 X 的仔细观察，他发现 $C$ 和 $E$ 满足特殊的条件：

$$C_i=\{\begin{array}{ll}x\times i& (x\times i\le K)\\ -K& \text{otherwise}\end{array}$$
$$E_i=\{\begin{array}{ll}y\times i& (y\times i\le K)\\ -K& \text{otherwise}\end{array}$$

小 Y 和小 Z 可以对这些落叶和雪花进行一些操作。每次，他们会选择满足价值之和 $\ge K$ 的一片落叶和一片雪花，然后让把它们一同组成一段彩色的回忆（Erinnerung）。之后，这片雪花和这片落叶就消失不见了，之后的操作也不能再用到这片雪花和落叶了。

小 X 想知道，他们最多能进行多少次操作。

输入格式

本题有多组数据。

第一行一个整数 $T$，表示数据的组数。

接下来 $T$ 行，每行三个非负整数 $x,y,K$。

输出格式

对于每组数据，输出一个整数，代表最多能有多少次操作。每组数据的答案用一个换行符隔开。

样例 #1

样例输入 #1

2
2 3 10
2 4 11

样例输出 #1

3
2

样例 #2

样例输入 #2

1
0 0 1

样例输出 #2

0

提示

【数据范围】

• Subtask 1（30 points）：$x,y,K,T\le 10$。
• Subtask 2（70 points）：无特殊限制。

对于 $100\%$ 的数据，满足 $0\le x,y\le 10^{10}$，$1\le K\le 10^{10}$，$1\le T\le 10^5$。

题解：

这道题我最开始的想法是枚举的，但是一看这数据量就知道这肯定有规律。于是就去看这个规律，那些大佬总结的我看的不是很懂，我讲讲我写的，

C数组大概是这样的

x 2x 3x … -k -k

E数组大概是这样的

y 2y 3y … -k -k

那么要是匹配的话最好就是从一个的最大开始，去对面找到最小可以匹配的数，枚举行不懂我们来看看数学规律。

假设最后一个为 nx,nx到k有多少呢，

k%x对吧，

那么对面大于k%x的最小数的系数是什么呢，

k%x/y对吧，

往后的都可以匹配那么就有 k/y-k%x/y个

但是要注意两边的个数是不等的，要取最小值

就有了 min(k / y - k % x / y, k / x - k % y / x)

然后呢要注意x,y为0的情况，还有就是x或y的倍数刚刚好就是k的时候

还有呢要注意开long long

好了上代码

#include <bits/stdc++.h>
using namespace std;
long long t, x, y, k;
int main()
{cin >> t;while (t--){cin >> x >> y >> k;if (x != 0 && y != 0)cout << min(k / y - k % x / y, k / x - k % y / x) << endl;else if (x == 0  && y != 0 && k % y == 0)cout << 1 << endl;else if (y == 0  && x != 0 && k % x == 0)cout << 1 << endl;else cout << 0 << endl;}return 0;
}