trang chủ / bài tập / twodivs

Hai ước số

Cho $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Với mỗi $a_{i}$ , hãy tìm hai ước số $d_{1} > 1$ và $d_{2} > 1$ của $a_{i}$ sao cho $gcd (d_{1} + d_{2}, a_{i}) = 1$ , hoặc thông báo rằng không tồn tại cặp ước như vậy.

Dữ liệu vào

Dòng đầu chứa số nguyên $n$ .
Dòng thứ hai chứa $n$ số nguyên $a_{1}, a_{2}, \dots, a_{n}$ .

Dữ liệu ra

In ra hai dòng, mỗi dòng gồm $n$ số nguyên:

Số thứ $i$ của dòng đầu và dòng thứ hai lần lượt là $d_{1}$ và $d_{2}$ tương ứng với $a_{i}$ (thỏa $d_{1} > 1$ , $d_{2} > 1$ , $d_{1} ∣ a_{i}$ , $d_{2} ∣ a_{i}$ và $gcd (d_{1} + d_{2}, a_{i}) = 1$ ).
Nếu không tồn tại cặp ước như vậy, in $- 1$ ở cả hai dòng tại vị trí $i$ .

Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ràng buộc

$1 \leq n \leq 5 \cdot 10^{5}$
$2 \leq a_{i} \leq 10^{7}$

Ví dụ

Input	Output	Giải thích
10 2 3 4 5 6 7 8 9 10 24	-1 -1 -1 -1 2 -1 -1 -1 2 8 -1 -1 -1 -1 3 -1 -1 -1 5 3	Với $a_{7} = 8$ : các ước lớn hơn $1$ là $2, 4, 8$ , tổng của mọi cặp đều chia hết cho $2$ nên không có đáp án. Với $a_{10} = 24$ : $gcd (8 + 3, 24) = 1$ ; các cặp khác như $(2, 3)$ hay $(3, 8)$ cũng hợp lệ.
5 12 1024 999983 49 6	4 -1 -1 -1 2 3 -1 -1 -1 3	$1024 = 2^{10}$ và $49 = 7^{2}$ chỉ có một ước nguyên tố, $999983$ là số nguyên tố, nên cả ba đều không có đáp án. Với $12$ : $gcd (4 + 3, 12) = 1$ .

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 7,00một phần

Giới hạn thời gian 1.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig