The Erdös-Straus Conjecture 题解

题面

Description

The Brocard Erdös-Straus conjecture is that for any integern > 2 , there are positive integersa ≤ b ≤ c,so that :

[{4over n}={1over a}+{1over b} +{1over c} ]

There may be multiple solutions. For example:

[{4over 18}={1over 9}+{1over 10}+{1over 90}={1over 5}+{1over 90}+{1over 90}={1over 5}+{1over 46}+{1over 2470} ]

Input

The first line of input contains a single decimal integer P, (1 ≤ p ≤ 1000), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number,K, followed by a single space, followed by the decimal integer n,(2 ≤ n ≤ 50000)

Output

For each data set there is one line of output. The single output line consists of the data set number, K, followed by a single space followed by the decimal integer values a, b and c in that order, separated by single spaces

Sample Input

Sample Output

1 4 18 468
2 133 23460 71764140
3 12463 207089366 11696183113896622
4 12463 310640276 96497380762715900
5 5 46 2070

题解

对于这个式子

[frac{4}{n}=frac{1}a+frac1b+frac1c ]

不如先解除(a)的范围，首先(a)必然大于(frac{n}4),因为(b和c)项不能为0，其次(a)要小于等于(frac{3*n}{4})，因为要满足字典序最小，(a)必然最小。然后我们在这个范围枚举(a)，计算可行的(b和c)，不如将(b和c)看成一个整体，这样可以解出(frac{1}{b}+frac{1}{c})

[frac{1}b+frac{1}c=frac{4*i-n}{n*i}(frac{n}{4} +1leq i leq frac{3*n}{4}) ]

如果解出后化简得到的分数正好分子为1，那么我们就可以直接得到(b和c)，我们假设解出的分数为(frac{x}{y},x=1),那么b和c就可以拆分为

[b=frac{1}{y+1} \ c=frac{1}{(y+1)*y} ]

如果化简后不为1，则从小到大枚举b，找到最小的c，枚举下界从解出的分数的倒数+1开始，保证(frac{1}{b} < frac{x}{y})到倒数的两倍结束，因为如果超过两倍的倒数b就大于c了，这时应轮换b和c使字典序最小，找出答案记录立刻退出循环即可

代码写的比较丑

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {
	return a % b == 0 ? b : gcd(b, a % b);
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int k; ll n;
		scanf("%d%lld", &k, &n);
		ll l = n / 4 + 1;
		ll r = n * 3 / 4;
		ll a, b, c;
		bool flag = false;
		for (ll i = l; i <= r; i++) {
			if (flag) break;
			ll x = n * i;
			ll y = 4 * i - n;
			ll num = gcd(x, y);
			x /= num;
			y /= num;
			if (y == 1) {
				a = i;
				b = x + 1;
				c = (x + 1) * x;
				flag = true;
				break;
			}
			else {
				ll s = x / y + 1;
				ll t = 2 * x / y;
				for (ll j = s; j <= t; j++) {
					ll tmp = y * j - x;
					if ((x * j) % tmp == 0) {
						a = i;
						b = j;
						c = x * j / tmp;
						flag = true;
						break;
					}
				}
			}
		}
		printf("%d %lld %lld %lld
", k, a, b, c);
	}
	return 0;
}

最近可能都没太有空更题解了，没做的题有点多，作业还好多wwww