题目SPJ有误(或者是数据水了)
查看原帖
题目SPJ有误(或者是数据水了)
894358
binomial楼主2025/5/5 15:08

RT.

题目要求了“从小到大输出”,但是实际上这份代码:

#include <math.h>
#include <stdio.h>
#include <stdbool.h>
#define ll long long
int a, b, mxd, s;
bool f;
ll ans[24], tmp[24];
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
bool check(int len) {
	if (ans[1] == 0) return 1;
	for (int i = len; i >= 1; i--) {
		if (tmp[i] == ans[i]) continue;
		else if (tmp[i] < ans[i]) return 1;
		else return 0;
	}
	return 0;
}
bool iddfs(int dep, ll a, ll b) {
	if (dep == mxd) {
		if (b % a) return 0;
		tmp[dep] = b / a;
		if (check(dep)) for (int i = 1; i <= dep; i++) ans[i] = tmp[i];
		return 1;
	}
	if (dep == mxd - 1) {
		// 最后两个数要满足 1 / x + 1 / y = a / b, 即 (x + y) / (x * y) = a / b
		// 可转化为 x + y = a * k , x * y = b * k
		// y = a * k - x, 代入后式 
		// x * x - a * k * x + b * k = 0
		// 该方程有解当且仅当 delta = a * a * k * k - 4 * b * k >= 0
		// 解得 k >= (4 * b) / (a * a)
		// 所以可以枚举 k , 找到某个 k 使得 sqrt(delta)为整数且解为整数 
		// 此时 x = (a * k - sqrt(delta)) / 2, y = (a * k + sqrt(delta)) / 2
		// 加入此优化即可通过, 讨论区的hack也可过 
		// 枚举的范围: a * k = x + y <= 2 * s, b * k = x * y <= s * s, delta > 0
		// 即 k <= 2 * s / a, k <= s * s / b, k > (4 * b) / (a * a) 
		for (int i = 4 * b / a / a + 1; i < min(2ll * s / a, 1ll * s * s / b); i++) {
			ll p = a * a * i * i - 4 * b * i, q = sqrt(p);
			if (q * q != p || (a * i + q) & 1) continue;
			tmp[dep] = (a * i - q) / 2, tmp[dep + 1] = (a * i + q) / 2;
			if (check(dep + 1)) for (int i = 1; i <= dep + 1; i++) ans[i] = tmp[i];
			return 1;
		}
		return 0;
	}
	int l = max(tmp[dep - 1], (b - 1) / a) + 1, r = (mxd - dep + 1) * b / a, g;
	bool flag = 0;
	for (int i = l; i < r; i++) {
		tmp[dep] = i, g = gcd(a * i - b, b * i);
		if (iddfs(dep + 1, (a * i - b) / g, b * i / g)) flag = 1;
	}
	return flag;
}
int main() {
	scanf("%d %d", &a, &b);
	while (!f) {
		s = 100, mxd++;
		//s为分母的上限 
		while (s < 10000000 && !f) s *= 10, f = iddfs(1, a, b);
	}
	for (int i = 1; i <= mxd; i++) printf("%d ", ans[i]);
	return 0;
}

样例会输出“6 5 18”,但是仍然通过。

2025/5/5 15:08
加载中...