洛谷P7441 Erinnerung

传送门

题目背景

我希望，
我们能留下存在过的痕迹，
然后优雅地离去，
无声地消逝。
我回想，
我们共同拥有的那些记忆：
我们随金色的落叶而聚，
又同白色的雪花而去。
或许什么也没有留下，
就要空手而归。
但我不必恐惧，
不需如此匆忙。
因为那些落叶和雪花，
永远地保存着，
我们书写的故事，
和无比珍贵的回忆。
—— lgswdn

题目描述

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

C_i=

C
i
​
={
x×i
−K
​

(x×i≤K)
otherwise
​

E_i=

E
i
​
={
y×i
−K
​

(y×i≤K)
otherwise
​

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

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

输入格式

本题有多组数据。

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

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

输出格式

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

输入输出样例

输入 #1复制
2
2 3 10
2 4 11
输出 #1复制
3
2
输入 #2复制
1
0 0 1
输出 #2复制
0

说明/提示

【样例解释】

对于样例 1 的第一组数据，落叶的价值为 2,4,6,8,10,-10,-10\dots2,4,6,8,10,−10,−10… ，雪花的价值为 3,6,9,-10,-10\dots3,6,9,−10,−10… 。第一次操作选取第 44 片落叶和第 11 片雪花，价值和为 1111。第二次操作选取第 22 片落叶和第 22 片雪花，价值和为 1010。第三次操作选取第 55 片落叶和第 33 片雪花，价值和为 1919。如是，可以进行 33 次操作。容易证明不存在更优的解。

对于第二组数据，进行的两次操作可以为：选取第 44 片落叶和第 11 片雪花，以及选取第 22 片落叶和第 22 片雪花。

对于样例 2，所有的雪花和落叶的价值都为 00，不可能找到落叶和雪花使其和 \ge 1≥1。

【数据范围】

Subtask 1（30 points）：x,y,K,T\le 10x,y,K,T≤10。
Subtask 2（70 points）：无特殊限制。
对于 100%100% 的数据，满足 0\le x,y\le 10^{10}0≤x,y≤10
10
，1\le K\le 10^{10}1≤K≤10
10
，1\le T\le 10^51≤T≤10
5
。

上代码：

#include
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		long long x,y,k;
		scanf("%lld%lld%lld",&x,&y,&k);
        if(x==0||y==0){//特判0
            if(x&&!(k%x))
                puts("1");
            else if(y&&!(k%y))
                puts("1");
            else
                puts("0");
        }
        else
			printf("%lld\n",k/max(x,y));
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21