3094081_tle.c

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>

__int64 num[20];
int cnt;
const int expr[] = {1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536};

int main()
{
	__int64 i, r, tmp, ans, small, big;
	__int64 gcd, lcm, bak;
	int j, l, max;

	while(scanf("%I64d%I64d",&gcd,&lcm)==2)
	{
		if(lcm == gcd)
		{
			printf("%I64d %I64d\n",gcd,lcm);
			continue;
		}
		lcm /= gcd;
		bak = lcm;
		cnt = 0;
		if(lcm % 2)
		{
			num[cnt] = lcm;
			while(lcm % 2 == 0)
			{
				lcm /= 2;
			}
			num[cnt++] /= lcm;
		}
		r = (__int64)(floor(sqrt(lcm)));
		for(i = 3; i <= r; i += 2)
		{
			if(lcm % i == 0)
			{
				num[cnt] = lcm;
				while(lcm % i == 0)
				{
					lcm /= i;
				}
				num[cnt++] /= lcm;
				r = (__int64)(floor(sqrt(lcm)));
			}
		}
		if(lcm != 1)
		{
			num[cnt++] = lcm;
		}
		max = 1 << cnt;
		ans = -1;
		for(j = 0; j < max; j++)
		{
			tmp = 1;
			for(l = 0; l < cnt; l++)
			{
				if((expr[l] & j) != 0)
				{
					tmp *= num[l];
				}
			}
			if(ans == -1 || gcd * (tmp + bak / tmp) < ans)
			{
				ans = (tmp + bak / tmp) * gcd;
				small = tmp * gcd;
				big = bak / tmp * gcd;
				if(small > big)
				{
					tmp = small;
					small = big;
					big = tmp;
				}
			}
		}
		printf("%I64d %I64d\n",small,big);
	}
	return 0;
}