题目描述
样例
输入
3
2023
63
1059872604593911
输出
17 7
3 7
104149 97711
参考代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstring>
#include <unordered_map>
#include <unordered_set>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#define IOS std::ios::sync_with_stdio(false)
#define inf 0x3f3f3f3f
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define int long long
#define x first
#define y second
//#define cmp [&](PII a, PII b){ return a.y < b.y; }
const int N = 5e5+10, mod = 1e9+7, M = 5e7+5, K = 2e5+10, Z = 1e5+7, X = 1.5 * 1e9;
using namespace std;
typedef long long LL;
typedef priority_queue<int> PQI;
typedef priority_queue <int, vector<int>, greater<>> PQGI;
typedef pair<int, int> PII;
int primes[M], cnt;
bool st[M];
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i + i; j <= n; j += i)
st[j] = true;
}
}
void solve()
{
// 题目中说给的用例一定有解,且唯一解,使题目难度降低,因为读错题目写了两种
int n; cin >> n;
for(int i = 0; i < cnt; i ++)
{
int t = primes[i];
if(n % t == 0)
{
n = n / t;
if(n % t == 0)
{
int a = t, b = n / t;
cout << a << ' ' << b << endl;
break;
}
else
{
int a = sqrt(n), b = t; // 题目中给说了有唯一确定的值,前面没看见唯一确定的值。
cout << a << ' ' << b << endl;
break;
}
}
}
// int t = pow(n, 0.333333333333333333);
// int s = lower_bound(primes + 1, primes + cnt + 1, t) - (primes + 1);
// for(int i = s; i <= cnt; i ++)
// {
// if(n % (primes[i] * primes[i]) == 0)
// {cout << primes[i] << ' ' << (n / (primes[i] * primes[i])) << endl; break;}
// }
return;
}
signed main()
{
IOS; cin.tie(0); cout.tie(0);
get_primes(3e6);
int T = 1;
cin >> T;
while( T -- ) solve();
return 0;
}