博客

题目描述

题意简述

给定一个n，求a,b(a+b=n&&LCM(a,b)最小)

算法描述

设x是n的因子，a=x，b=n-x,那么就有max(a,b)%min(a,b)=0

那么a，b的最大公倍数便是max(a,b)

因为a+b=n,那么a越大，b越小，始终保证a为n的因子，即a<n/2,所以尽量增大a减小b便可使LCM(a,b)变小，找出最大的因子即可

代码

#include <cstdio>
 
int main()
{
	int t; scanf("%d",&t);
	while(t--)
	{
		int n,p; scanf("%d",&n); p=n;
		for(int i=2; i*i<=n; i++) if(n%i==0)
		{
			p=i; break;
		}
		printf("%d %d\n",n/p,n-n/p);
	}
	return 0;
}