2024.9.27校测

JPGOJCZX / 2024-09-28 / 原文

T1

题目描述

$Mr.Hu$ 开了个饭店，来了两位客人：$Alice$ 和 $Bob$，他们吃完饭要结账时，发现他们需要支付 $c$ 元钱，但是 $Alice$ 只有面值为 $a$ 的钱，$Bob$ 只有面值为 $b$ 的钱（他们每个人的钱的和都大于 $c$, 即可以认为他们有无数张对应面值钱）。现在，$Mr.Hu$ 想知道，他们可能刚好支付完饭钱吗？如果可能，那么有多少种方式？你还需要计算出他们所有可能的支付方式的支付的钱的张数的和。

输入格式

第 $1$ 行包含 $2$ 个整数：$T, opt$，其中 $T$ 表示数据组数，$opt$ 为数据类型。

接下来 $T$ 行，每行 $3$ 个整数：$a, b, c$。

输出格式

对于每组数据：

如果 $opt = 1$，输出一行，包含一个整数：$A$，其中 $A$ 表示刚好支付的方案数。
如果 $opt = 2$，输出一行，包含两个整数：$A, B$，其中 $A$ 表示刚好支付的方案数，$B$ 表示所有可能
支付方式的张数和。

输入样例1

2 2
3 4 21
2 4 12

输出样例1

2 13
4 18

样例1解释

对于 $3, 4, 21$，一共有两种可能的支付方式，分别是：$(3, 3), (7, 0)^1$，所以 $A$ 为 $2$，$B$ 为 $3 + 3 + 7 + 0 = 13$。

对于 $2, 4, 12$，一共有四种可能的支付方式，分别是：$(6, 0), (4, 1), (2, 2), (0, 3)$，所以 $A$ 为 $4$，$B$ 为
$6 + 0 + 4 + 1 + 2 + 2 + 0 + 3 = 18$。

输入样例2

2 1
3 4 21
2 4 12

输出样例2

2
4

数据规模

对于 $20\%$ 数据，$1 \leq a, b, c \leq 10000, 1 \leq T \leq 1000$。

对于另外 $40\%$ 数据，$1 \leq a, b, c \leq 10^9$，其中 $opt = 1$。

对于另外 $40\%$ 数据，$1 \leq a, b, c \leq 10^9$，其中 $opt = 2$。

对于 $100\%$ 数据，$1 \leq T \leq 10^5, 1 \leq opt \leq 2$。

题解

设 $Alice$ 要支付的钱的张数为 $x$ ($x \geq 0$)，$Bob$ 要支付的钱的张数为 $y$ ($y \geq 0$)，那么可以写出如下二元一次不定方程 $ax + by = c$，根据数论学习笔记（一）（2024.7.25），当且仅当 $\gcd(a, b) \mid c$ 时才有解。

考虑 $x$ 和 $y$ 都要大于 $0$，那么将 $x$ 变为最小的满足条件的非负整数时，如果 $y$ 仍未非正整数，那么也是凑不出这么多钱的。

以上两种情况是无解的，直接输出 $0$，如果有 $x$ 和 $y$ 都为非负整数的解，那么考虑通解 $x = x_0 + (b / d)n, y = y_0 - (a / d)n$。

考虑到将 $x$ 变为最小值时 $y$ 已是最大值，所以 $\lfloor\displaystyle\frac{y}{a / d}\rfloor + 1$ (加 $1$ 是因为可以一个 $a / d$ 也不减) 就是方案数。

考虑每变化一次张数会变大或变小 $| a / d - b / d |$，且要么一直变大，要么一直变小，可以发现这是一个等差数列，所以只需要将总张数最大和总张数最小的情况算出，就可以套用等差数列求和公式来求解张数。

完整代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
int extend_gcd(int a, int b, int &x, int &y){
	if(b == 0){
		x = 1;
		y = 0;
		return 0;
	}
	int d = extend_gcd(b, a % b, y, x);
	y -= a / b * x;
	return d;
}
int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}
int T, opt, a, b, c;
signed main(){
	freopen("pay.in", "r", stdin);
	freopen("pay.out", "w", stdout);
	scanf("%lld%lld", &T, &opt);
	while(T--){
		scanf("%lld%lld%lld", &a, &b, &c);
		if(c % gcd(a, b) != 0){
			if(opt == 1)
				printf("0\n");
			else
				printf("0 0\n");
			continue;
		}	
		int d = gcd(a, b);
		int x, y;
		extend_gcd(a, b, x, y);
		x *= c / d;
		y *= c / d;
		int dis;
		if(x < 0){
			dis = ceil((-x) * 1.0 / (b / d));
			x += dis * (b / d);
			y -= dis * (a / d);
		} else {
			dis = floor(x * 1.0 / (b / d));
			x -= dis * (b / d);
			y += dis * (a / d);
		}
		if(y >= 0){
			printf("%lld", y / (a / d) + 1);
			if(opt == 1)
				printf("\n");
			else {
				printf(" ");
				int ans1 = x + y, ans2 = y % (a / d) + x + y / (a / d) * (b / d);
				int ans = (ans1 + ans2) * (y / (a / d) + 1) / 2;
				printf("%lld\n", ans);
			}
		} else {
			if(opt == 1)
				printf("0\n");
			else
				printf("0 0\n");
			continue;
		}
	}
	return 0;
}