/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君はレストランの店員です。お客様が来るたびに、テーブルの上にできるだけ大きな正方形のテーブルクロスを敷きたいと考えています。
レストランには長方形のテーブルがいくつかあります。各テーブルの天板は 1 \times 1 の小さなマス目で区切られており、マス目の総数が N 個であることは分かっています。つまり、テーブルの大きさは a \times b （ a \times b = N , a, b は正の整数）の長方形ですが、具体的な a と b の値は記録されていません。
高橋君は、テーブルの上に正方形のテーブルクロスを 1 枚敷きます。テーブルクロスの大きさは s \times s （ s は正の整数）で、テーブルからはみ出してはいけないため、 s \leq a かつ s \leq b でなければなりません。したがって、テーブルの形が a \times b のとき、敷ける正方形の最大サイズは s = \min(a, b) です。
a と b の値が分からないため、高橋君はどのような形のテーブルであっても確実に敷ける最大の正方形サイズを知りたいのではなく、 最も都合の良いテーブルの形を想定したとき に敷ける正方形の最大サイズを知りたいと思っています。
すなわち、 a \times b = N を満たすすべての正の整数の組 (a, b) について \min(a, b) を考えたとき、その 最大値 を求めてください。
言い換えると、 N を 2 つの正の整数の積 a \times b として表すすべての方法のうち、 \min(a, b) が最大となるものを見つけ、そのときの \min(a, b) の値を出力してください。
Q 個のクエリが与えられるので、それぞれについて答えてください。
制約
- 1 \leq Q \leq 100
- 1 \leq N_i \leq 10^{12}
- 入力はすべて整数である。
入力
Q N_1 N_2 : N_Q
- 1 行目には、クエリの個数を表す Q が与えられる。
- 2 行目から Q 行では、各クエリにおけるマス目の総数 N_i が 1 行に 1 つずつ与えられる。
出力
Q 行出力せよ。 i 行目には、 N_i に対する答え、すなわち a \times b = N_i を満たす正の整数の組 (a, b) における \min(a, b) の最大値を出力せよ。
入力例 1
3 12 6 4
出力例 1
3 2 2
入力例 2
4 7 9 16 24
出力例 2
1 3 4 4
入力例 3
5 1000000 999999 100000 123456 720720
出力例 3
1000 999 250 192 840
入力例 4
5 1000000000000 999999999999 999961000039 100000000019 864691128000
出力例 4
1000000 999999 1 1 921060
入力例 5
3 12 6 4
出力例 5
3 2 2
入力例 6
4 7 9 16 24
出力例 6
1 3 4 4
入力例 7
5 1000000 999999 100000 123456 720720
出力例 7
1000 999 250 192 840
入力例 8
5 1000000000000 999999999999 999961000039 549755813888 100000000003
出力例 8
1000000 999999 1 524288 1
入力例 9
5 1 2 3 1000000000000 997799779977
出力例 9
1 1 1 1000000 907907
Score : 300 pts
Problem Statement
Takahashi is a restaurant employee. Every time a customer arrives, he wants to spread the largest possible square tablecloth on the table.
The restaurant has several rectangular tables. Each table's surface is divided into small 1 \times 1 cells, and it is known that the total number of cells is N. In other words, the table size is a rectangle of a \times b (where a \times b = N, and a, b are positive integers), but the specific values of a and b are not recorded.
Takahashi will spread one square tablecloth on the table. The tablecloth size is s \times s (where s is a positive integer), and since it must not hang over the edge of the table, we need s \leq a and s \leq b. Therefore, when the table shape is a \times b, the maximum square size that can be spread is s = \min(a, b).
Since the values of a and b are unknown, Takahashi does not want to find the maximum square size that can surely be spread regardless of the table shape. Instead, he wants to find the maximum square size that can be spread when assuming the most favorable table shape.
That is, considering \min(a, b) for all pairs of positive integers (a, b) satisfying a \times b = N, find the maximum value.
In other words, among all ways to express N as a product a \times b of two positive integers, find the one that maximizes \min(a, b), and output that value of \min(a, b).
You are given Q queries. Answer each of them.
Constraints
- 1 \leq Q \leq 100
- 1 \leq N_i \leq 10^{12}
- All inputs are integers.
Input
Q N_1 N_2 : N_Q
- The first line gives Q, the number of queries.
- From the second line through the next Q lines, the total number of cells N_i for each query is given, one per line.
Output
Output Q lines. On the i-th line, output the answer for N_i, that is, the maximum value of \min(a, b) over all pairs of positive integers (a, b) satisfying a \times b = N_i.
Sample Input 1
3 12 6 4
Sample Output 1
3 2 2
Sample Input 2
4 7 9 16 24
Sample Output 2
1 3 4 4
Sample Input 3
5 1000000 999999 100000 123456 720720
Sample Output 3
1000 999 250 192 840
Sample Input 4
5 1000000000000 999999999999 999961000039 100000000019 864691128000
Sample Output 4
1000000 999999 1 1 921060
Sample Input 5
3 12 6 4
Sample Output 5
3 2 2
Sample Input 6
4 7 9 16 24
Sample Output 6
1 3 4 4
Sample Input 7
5 1000000 999999 100000 123456 720720
Sample Output 7
1000 999 250 192 840
Sample Input 8
5 1000000000000 999999999999 999961000039 549755813888 100000000003
Sample Output 8
1000000 999999 1 524288 1
Sample Input 9
5 1 2 3 1000000000000 997799779977
Sample Output 9
1 1 1 1000000 907907