102843: [AtCoder]ABC284 D - Happy New Year 2023

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

You are given a positive integer $N$. It is known that $N$ can be represented as $N=p^2q$ using two different prime numbers $p$ and $q$.

Find $p$ and $q$.

You have $T$ test cases to solve.

Constraints

  • All values in the input are integers.
  • $1\leq T\leq 10$
  • $1\leq N \leq 9\times 10^{18}$
  • $N$ can be represented as $N=p^2q$ using two different prime numbers $p$ and $q$.

Input

The input is given from Standard Input in the following format, where $\text{test}_i$ represents the $i$-th test case:

$T$
$\text{test}_1$
$\text{test}_2$
$\vdots$
$\text{test}_T$

Each test case is in the following format:

$N$

Output

Print $T$ lines.

The $i$-th $(1\leq i \leq T)$ line should contain $p$ and $q$ for the $i$-th test case, separated by a space. Under the constraints of this problem, it can be proved that the pair of prime numbers $p$ and $q$ such that $N=p^2q$ is unique.


Sample Input 1

3
2023
63
1059872604593911

Sample Output 1

17 7
3 7
104149 97711

For the first test case, we have $N=2023=17^2\times 7$. Thus, $p=17$ and $q=7$.

Input

题意翻译

给定一个正整数 $N\le 9\times 10^{18}$,保证 $N=p^2q$ 且 $p,q$ 均为质数,请求出 $p,q$。 翻译 by @Mars\_Dingdang

Output

分数:400分

问题描述

给你一个正整数$N$。已知$N$可以用两个不同的质数$p$和$q$表示为$N=p^2q$。

找出$p$和$q$。

你需要解决$T$个测试用例。

约束

  • 输入中的所有值都是整数。
  • $1\leq T\leq 10$
  • $1\leq N \leq 9\times 10^{18}$
  • $N$可以用两个不同的质数$p$和$q$表示为$N=p^2q$。

输入

输入从标准输入以以下格式给出,其中$\text{test}_i$表示第$i$个测试用例:

$T$
$\text{test}_1$
$\text{test}_2$
$\vdots$
$\text{test}_T$

每个测试用例的格式如下:

$N$

输出

打印$T$行。

第$i$行($1\leq i \leq T$)应包含第$i$个测试用例的$p$和$q$,由空格分隔。 在本问题的约束条件下,可以证明满足$N=p^2q$的质数对$p$和$q$是唯一的。


样例输入1

3
2023
63
1059872604593911

样例输出1

17 7
3 7
104149 97711

对于第一个测试用例,我们有$N=2023=17^2\times 7$。因此,$p=17$,$q=7$。

加入题单

上一题 下一题 算法标签: