SPOJ.com - Problem PRIMEPOW

PRIMEPOW - Prime Power Test

no tags

Finite fields only exist when the order (size) is a prime power p^k (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.

Input

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

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=p^k. Else output "Invalid order".

Example

Input:
3
6
7
8

Output:
Invalid order
7 1
2 3

Constraints

For the hardest input files : T about 100, and 1 < N < 2²⁰¹⁴, N are 2¹²⁸-smooth numbers. (Thanks at Min_25 for suggesting this constraint). About 50% of input cases are "Invalid order".
For the easiest input files : T about 10000, and 1 < N < 2⁶⁴.

Edit 2017-02-11 : TL updated ; compiler changes

Submit solution!

hide comments



	Michael Kharitonov: 2017-02-02 21:38:42 @Francky, how close am I to AC? My first Python code in a long time. =(Francky)=> You're very close to AC. Same as some other psolvers here, your solution lack a specific point to speed up some cases. You'll find it ;-) =(Michael)=> Thanks, got AC. I'm curious, I fixed the right specific point or were you talking about something else? =(Francky)=> I didn't read your code, but it seems you improved all cases speed, and in particular the desired one. Congrats for your AC. Last edit: 2017-02-03 13:54:42
	testing java: 2017-01-03 22:29:05 It is really frustrating. I don't even know whether there is some bug in code (I don't use python everyday, but this problem forced me to use it, thus some bugs are likely), or is my primality test not good enough for given testcases. Right now, can't find any counter-example to work with. [POSSIBLE SPOILER] Is 'factorize maximal exponent k such that m^k = n and check whether m is prime' approach bad? =(Francky)=> I didn't read your code, but I can tell you that a probabilistic prime test may fail to my test cases, as I know how to generate strong pseudo-primes. You may need a deterministic variant of a probabilistic one. Good luck. edit : now you have AC on almost all input files ; you have TLE only on specific cases, where a faster method is required. Last edit: 2017-01-10 09:43:51
	copperfield42: 2016-09-20 01:13:44 I only register to solve this and it was a fun little problem, not bad for my first try this site, I guess. @Francky Any suggestion about my code? =(Francky)=> Your code is quite the desired solution ; here there are faster AC, but they are legend coders. Congrats for your AC here, and thanks for your appreciation. If you like those kind of problems, take a look at my problems page... Last edit: 2016-09-20 17:43:12
	[Lakshman]: 2016-06-27 10:31:15 I tried this problem again with different logic and tested it on ideone with random test cases it is taking around 10s on ideone for T=100 and n <=(22014) here it is giving TLE. (Spoj cluster is 2x faster than ideone). =(Francky)=> You have a similar speed than my own PY3.4 code on all files, unless the last one that is made of 'special cases' and you have to find what can be the special cases, and how to deal with them. Good luck. Last edit: 2016-06-27 11:06:11**
	JY: 2016-03-16 17:52:42 I don't know why I get tle. For worst case(T=100, N=22014-1(which gives invalid input)) , my code takes 8 seconds. Can you please tell more about time limit on various test files ? =(Francky)=> You have TLE only for one easy input file ; at 1s. For the others you have slow but AC flag. Good luck, you're not so far. (jatin) => The T=10000,N=264-1 (worst case for easy input) runs in 0.5 seconds on my pc. Can you please tell the details of test file I am failing? (T, constraints on N). Thanks :) Last edit: 2016-06-17 07:38:29
	Viplov Jain: 2015-02-12 13:25:18 @Francky help with with the WA's. cant find the error (Francky) => I'll build a new problem soon for people (like you) that are doing the same mistake. I'll try it within a week ; I'm not for now available ; please be patient. Last edit: 2020-09-26 17:56:53
	[Lakshman]: 2015-01-23 04:50:20 @Francky can you please publish a tutorial version of this problem with relaxed time limit. Thanks. --Francky--> I'll do something, I hope soon. Last edit: 2015-01-23 21:38:08
	[Lakshman]: 2015-01-11 06:26:44 @Francky Can you please tell me about two of my submission for #13396009 can we get AC with this method. #13396182 I got WA for this. I think in this I am very close to AC. Thanks. --(Francky)--> You are very near, it's true. I'll make a problem that will be helpful for the last details. --Lakshman->Thanks @Francky Last edit: 2015-01-11 15:56:34
	[Lakshman]: 2014-12-23 19:37:29 @Francky can you please have a look on my last submission now I am getting wrong answer. --ans(Francky)--> You have few WA, but for at least two reasons (I think). Good luck, you're not so far. --Lakshman--> Thanks for your reply. But once again even after trying hard I can't make it AC. Last edit: 2014-12-24 06:55:16
	[Lakshman]: 2014-12-14 16:12:44 @Francky any suggestion for optimization? --ans(Francky)--> Build several kind of possible input, then find those that are 'problematic', then work first on theses cases. This should be a good advice for any problem ;-) Last edit: 2014-12-23 19:36:16

Submit solution!

Added by:	Francky
Date:	2014-12-12
Time limit:	1s-10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	Number theory