SPOJ.com - Problem PSYCHOT

PSYCHOT - Psycho34 (easy)

no tags

In the prime factorization of a number N, there's two kinds of powers. Even powers, in red, are psychotic ones, and odd powers, in blue, are ordinary ones.
We'll say N a Psycho number if the count of even powers is strictly greater than the count of odd powers, else an Ordinary number.
For example, if N = 67500 with prime factorization 67500 = 2² x 3³ x 5⁴ .
This number have 2 even powers and 1 odd power. Since 2>1, so the number 67500 is a Psycho Number.

Input

The first line of input contains an integer T, the number of test cases.

Each of the next T lines contains one integer N.

Output

For each test case, print if N is Psycho or Ordinary number.

Example

Input:
2
3
4

Output:
Ordinary Number
Psycho Number

Constraints

0 < T < 10^4
1 < N < 10^14

Time limit is ×2 my top speed with Python3 language, it could be not easy with slow languages.
O(N^.5 / log(N)) should give TLE even with fast languages. You are awaited to submit something between O(N^0.33 / log(N)) and O(N^0.25 / log(N)). You can try before the quite similar "tutorial" problem : Psycho before.
@speed addicts : my top C timing is 0.02s. (TL updated 2017-02-11 ; compiler changes)

Submit solution!

hide comments

< Previous 1 2 Next >

	[Lakshman]: 2014-05-22 19:40:47 On the top now it is 0.05;) --(Francky)--> Congratulations ! (My trick is simpler than yours, but in the same spirit) Very good job. Last edit: 2014-05-22 19:55:04
	[Lakshman]: 2014-05-15 07:16:09 @Mitch Schwartz Yes I have checked many hand made strong cases with my AC and the last submitted code. Okay I will test for more cases. --ans(Francky)--> ~~Avoid random cases~~ ; try to build on your own tricky cases : eg p, p², p²q, pqr, p⁴, p²q², p²q²r, ... (with big primes) ; good luck. But, again, you should strongly begin with Mitch advice. In many problems it is easy to build a brute force and check random or small cases. My first answer supposed you've done a serious random test. But now I'm not sure... --Lakshman--> finally got the mistake Now Accepted. really enjoyed this problem and finally found the new method. --(Francky)--> OK, you almost found the new method ; a simpler one you may admit ;-))) But there's another trick that seriously boost the answer 'most' of the time... Good luck. --Lakshman--> Okay I will try to find that simpler one. Last edit: 2014-05-24 12:02:17
	Mitch Schwartz: 2014-05-15 06:19:17 @Lakshman, have you generated some random tests and compared output between your old AC and your new WA code?
	[Lakshman]: 2014-05-15 05:33:42 @Francky Can you please have a look on my last submission, I have used trial division but getting WA. Thanks.
	wisfaq: 2014-05-14 10:43:34 Personally I think that moving a 7 month old classical problem to tutorial because a EB member has made a more challenging version smells like "detournement du pouvoir" One should at least consult the members what they think about such a move. What if we start creating more challenging versions for every problem in classical and move the original one to tutorial however long it has been arounnd? I think it better to keep both in classical simply because the simpler one has been around for such a long time. What harm is done by keeping both in classical? --ans(Francky)--> I can hear that, and I can "mettre de l'eau dans mon vin" ;-) (and I've consulted before acting too, ...) --ans(wisfaq) Thanks for reverting your action. Last edit: 2014-05-14 12:24:21
	[Lakshman]: 2014-05-14 08:43:52 Let me check with my python code. Don't know how to AC with python even O(N^0.25) with PYTHON is giving TLE. --ans(Francky)--> Here a simpler method than Rho-Pollard is much faster. Think simple ; problem designed to be solved with only a sieve, trial divisions, and a good is_prime. --Lakshman-> Still I have no idea how to AC with trial division+sieve can you check my submission ::11573616 My sieve took .01s on cube cluster for prime till 10^7 and doing normal trial division but still tle. Is there other kind of trial division or am I doing something wrong. --ans(Francky)--> You can stop at some specific point after a quick check. That made it much faster. Last edit: 2014-05-14 12:11:41
	[Lakshman]: 2014-05-14 08:36:19 @Francky good constraints and Time limit. definitely not an easy even with fast language, even O(N^0.3) is getting TLE with fast language. we need O(N^0.25) for AC. Good for classical section. EDIT:: MY Best time with C++ 0.05s Last edit: 2014-05-23 10:53:31

Submit solution!

Added by:	Francky
Date:	2014-05-14
Time limit:	1.200s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	PSYCHON