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”,但是仍然通过。