CSU 2276 The Erdös-Straus Conjecture 暴力

http://acm.csu.edu.cn:20080/csuoj/problemset/problem?pid=2276

Description

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

 

4n=1a+1b+1c4n=1a+1b+1c

There may be multiple solutions. For example:

418=19+110+190=15+190+190=15+146+12470418=19+110+190=15+190+190=15+146+12470

Since it is still a conjecture, there are obviously no counterexamples forn ≤ 50, 000.For this problem, you will write a program which takes as input an integer n between 2 and 50000 inclusive and returns the smallest triple of integers a, b, c in lexicographic order which satisfies equation (1) above. That is, if a1, b1, c1 is any other solution to (1) for the given input, then either (a < a1) or (a = a1 andb ≤ b1).

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

5
1 13
2 529
3 49849
4 49850
5 18

Sample Output

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

Hint

Source

题目大意：给出n，找出a、b、c满足4/n=1/a+1/b+1/c且a<=b<=c。输出字典序最小的那组解即可。

思路：比赛的时候确实没怎么想这道题，看了题解才知道暴力搜索就行了orz。由条件a<=b<=c我们可以限定a的范围：[4/n+1，3*n/4]，然后在这个范围内枚举a的值，从而得到等式：1/b+1/c=(4*a-n)/(n*a)，我们令t1=4*a-n，t2=n*a，即1/b+1/c=t1/t2(这里要化简)，因为b<=c，所以1/b>=1/c，从小到大枚举b，即从大到小枚举1/b，而max(1/b)<t1/t2，即min(b)>t2/t1，因此我们从t2/t1+1开始枚举b，枚举到2*t2/t1即可(此时b=c)，此时a和b的值已经确定，那么我们得到等式：1/c=(t1*b-t2)/(t2*b)，从而发现当(t2*b)%(t1*b-t2)=0时，就找到了一组字典序最小的解。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

ll a,b,c,t1,t2,n;
int t,times;

ll gcd(ll x,ll y)
{
	return y==0?x:gcd(y,x%y);
}

int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d %lld",&times,&n);
		ll m1=n*3/4;
		for(ll i=n/4+1;i<=m1;i++)
		{
			t1=4*i-n;
			t2=n*i;
			ll g=gcd(t1,t2);
			t1/=g;
			t2/=g;
			ll m2=2*t2/t1;
			bool flag=0;
			for(ll j=t2/t1+1;j<=m2;j++)
			{
				if((t2*j)%(t1*j-t2)==0)
				{
					flag=1;
					printf("%d %lld %lld %lld\n",times,i,j,(t2*j)/(t1*j-t2));
					break;
				}
			}
			if(flag)
				break;
		}
	}
	return 0;
}