PRIMPOW2 - Prime Power Test (Hard)
Finite fields only exist when the order (size) is a prime power pk (where p is a prime number and k is a positive integer). For each prime power, there is a finite field with this size, and all fields of a given order are isomorphic. Finite fields are fundamental in a number of areas of mathematics and computer science, including number theory, algebraic geometry, Galois theory, finite geometry, cryptography and coding theory.
The first line contains an integer T, the number of test cases. On the next T lines, you will be given an integer N : a proposed order to be tested.
Output T lines, one for each test case, with p k if N can be the order of a finite field. p must be a prime number, and k an integer such that N=pk. Else output "Invalid order".
Input: 3 6 7 8 Output: Invalid order 7 1 2 3
T about 27, and 1 < N < 233333, N are 2128-smooth numbers. (Thanks at Min_25 for suggesting this constraint). About 50% of input cases are "Invalid order". N is log-uniform distributed between 233333 and its square root. Prime numbers in N decomposition are almost log-uniform distributed, from 4bit to 128bit. 3 input files. You may first try PRIMEPOW with easier constraints.
Edit(2017-02-11) TL updated ; compiler changes.
@francky I did some changes in my old code and got AC in PRIMEPOW and my complexity is quite good
@Francky I am stuck, I solve the first one but the same solution don't work here why is that??