B. Omkar and Last Class of Math

In Omkar’s last class of math, he learned about the least common multiple, or LCMLCM. LCM(a,b)LCM(a,b) is the smallest positive integer xx which is divisible by both aa and bb.

Omkar, having a laudably curious mind, immediately thought of a problem involving the LCMLCM operation: given an integer nn, find positive integers aa and bb such that a+b=na+b=n and LCM(a,b)LCM(a,b) is the minimum value possible.

Can you help Omkar solve his ludicrously challenging math problem?Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤101≤t≤10). Description of the test cases follows.

Each test case consists of a single integer nn (2≤n≤1092≤n≤109).Output

For each test case, output two positive integers aa and bb, such that a+b=na+b=n and LCM(a,b)LCM(a,b) is the minimum possible.ExampleinputCopy

3
4
6
9

outputCopy

2 2
3 3
3 6

Note

For the first test case, the numbers we can choose are 1,31,3 or 2,22,2. LCM(1,3)=3LCM(1,3)=3 and LCM(2,2)=2LCM(2,2)=2, so we output 2 22 2.

For the second test case, the numbers we can choose are 1,51,5, 2,42,4, or 3,33,3. LCM(1,5)=5LCM(1,5)=5, LCM(2,4)=4LCM(2,4)=4, and LCM(3,3)=3LCM(3,3)=3, so we output 3 33 3.

For the third test case, LCM(3,6)=6LCM(3,6)=6. It can be shown that there are no other pairs of numbers which sum to 99 that have a lower LCMLCM.

---

题意：有n=a+b,求lcm(a,b)最小时的a和b

先说下自己昨晚的相错的地方，找规律找出来是和因数有关，并且觉得是最大因数，但是自己却从sqrt(n)倒着去找最大的因数…但是实际上，因子对称分布在sqrt(n)的两边，所以以后要求n的最大因数，在O（sqrt）的情况下，找到他的最小的因子(>=2/特判)，然后用n/最小因子来得到最大因子。

但是实际上并不用分这么多..只是自己当时想的时候往奇数偶数再判奇数的素/合去思考了。

那看了题解之后我们证明一下：

令所求表达式lcm为lcm(k,n-k)且假设k<=n-k，得出k<=n/2;

那么有两种情况，一种是k|n,另一种是k~|n;

1.若k|n,则k|n-k,那么由于k<=n-k,所以minlcm(k,n-k)=n-k;

2.若k~|n,那么k~|n-k,那么lcm(k,n-k)必须是(n-k)和k的倍数并且k~|n-k;

那么这个k最小取2。当k=2时有如下：k*(n-k)>=2(n-k)>=2(n-n/2)>=n;

综上，k必然是n的因数。那么我们要n-k最小化，就让k最大化。于是就是最上面的自己昨晚想错的部分

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5;
typedef long long LL;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
LL primes(LL x)
{
	for(LL i=2;i<=sqrt(x);i++)
	{
		if(x%i==0)//如果是合数 
		{ 
			return 0;
		}
	}
	return 1;
}
LL get(LL x)
{
	for(LL i=2;i<=sqrt(x);i++)
	{
		if(x%i==0)
		{
			return i;
		}
	}
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--)
  {
  	LL n;cin>>n;
  	if(n%2==0)
  	{
  	  cout<<n/2<<" "<<n/2<<endl;
	}
	else if(n%2==1)
	{
		
		if(primes(n)) cout<<1<<' '<<n-1<<endl;//若是质数 
		else{
			LL k=get(n);
			cout<<n/k<<' '<<n-n/k<<endl;
		}		
	}
  }
return 0;
}