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 >

	fairooj_04: 2020-04-25 18:01:01 @Isha_31 can you help me here? I've got correct answer in my laptop and ideone it but here it's saying runtime error (SIGFPE)
	anonymous: 2018-02-24 08:02:29 @Francky：I have passed this problem with a method whose time complexity is O(n^(1/3)/log(n)). But I have no idea about how to solve it in O(n^(1/4)/log(n)). Could you give me some hints? Thanks. =(Francky)=> You could figure what could be various input numbers and use various methods on them. Eg, if you have yet partially factors of n, maybe at some point you don't need to know the final factors. Not only when it remains only two (equal or not) factors. Moreover, you could speed up the small factor part, ... @Francky：Thank you for your hints, but sadly I still can't work it out. Is your solution O(n^(1/4)/log(n)) constantly or in a part of situations? I get stuck in such a situation: n=4x, and the smallest prime factor of x is larger than n^(1/4). =(Francky)=> In such cases, my solution is O(n^(1/3)/log(n)) ; a part of input... @Francky：Thanks. Now I know the meaning of "between O(N^0.33 / log(N)) and O(N^0.25 / log(N))". I have thought about how to do it in O(n^(1/4)/log(n)) constantly only with a sieve, trial divisions and a good is_prime for a few days. It's a right choice to ask you. Last edit: 2018-02-27 05:52:24*
	Sayak Haldar: 2015-03-13 13:54:41 Yes, trial division(an approach between N1/3 and N1/4),sieve and good isprime function(rabin_miller with iteration upto 18 to eliminate all strong pseudoprimes) would pass it only with good observation(and heavy optimizations accordingly(I managed with scanf and printf)) But I am still unaware about the trick to solve it within 0.05 sec)
	Sayak Haldar: 2015-03-09 15:27:48 Francky,Would you please tell me If I use Radin Miller Priamalty test how much iterations would suffice the job for numbers less than N<10^14 and is there any WA in the TLE solution in the solution id 13846476 ? I exactly come up with an trial division algo with timte complexity between N1/4 and N1/3 and Rabin_Miller wih iteration 18... EDIT: Finally got it with heavy optimization tricks(almost after 15 or 16 WA and TLE solutions) Last edit: 2015-03-13 13:50:14
	Vikneshwar E: 2015-01-27 21:07:26 I have got Psychon solution accepted. But here I am getting wrong answer. Could someone please help me in figuring out the mistake.Submission ID 13534827 --Francky--> You have only few mistakes. @Francky : Thanks for the reply. But am I doing mistake in preprocessing or in determining whether the number is psychon? I assume the part of coding for psychon is correct since I got it accepted already. Could you please tell me which part I am doing mistake . Any hint regarding the mistake ? --Francky--> Determining psyco or not is trivial task, you can't have AC at 'PSYCO' pb without have this part correct ; so obviously your error is in the first part, preprocessing. Last edit: 2015-01-27 21:45:12
	Vikneshwar E: 2015-01-27 20:03:06 @Francky : Submission ID 13534827 . I am getting Wrong ans. Could you please help me to figure out where I am doing mistake ? Last edit: 2015-01-27 21:10:05
	varun: 2014-10-22 22:22:55 Can someone check my solution, submission id: 12699398. I am using sieve of Sundaram + primality Test + Trial division. still getting TLE. Am I missing something? --ans(Francky)--> Yes, you can make it simpler. You have too WA... --varun--> I think reducing the no. of iterations costed me WA while increasing it is leading to TLE. Seeing the Time limit and input size, I was inclined towards rho-pollard or fermat factorization but you mentioned problem is designed to be solved with sieve + Trial division + isPrime. Best solution clocks 0.05s that's hard to believe, I don't seem to have slightest of idea as how can I get even close to 0.05 with trial division. I'll try to dive deep and figure out how can I optimize. --(varun)--> as suggested I made it simple, but I am still unable to meet the time limits. Is it possible for you to take a look at my last submission and point where I can optimize? Last edit: 2014-11-01 20:37:29
	XeRoN!X: 2014-06-07 09:37:01 (easy) tag is fine considering the test cases. With N < 10^14 i am surprised how all solutions are incredibly fast. --ans(Francky)--> You simply missed a specific trick here to seriously boost algo and give sooner an answer ;-) We don't need to fully factorize some numbers... It is not related to weakness of input file and their cases. It's a part of the problem. (re:xeronix) : Thanks, got it. few more lines of code reduced the time significantly. --Francky--> Well done ;-) Last edit: 2014-06-07 13:06:00
	[Lakshman]: 2014-05-25 16:40:33 @Francky I think test cases need to be updated. Or we should think about n<=10^18. --> This problem is of very poor interest (I didn't put it in my problem list...). For n higher, there's yet good factoring problems. No need to multiply them at infinity. For those who find a problem easy : just try it with a slower languages, if it's still too easy, then try FACT2. (Edit Francky) Or the great problem NUMTRY. Last edit: 2014-06-07 10:11:41
	fitcat: 2014-05-23 07:22:43 @Francky: The test cases are not strong enough. My previous submissions incorrectly treated 202905198900 as an Ordinary number but got AC. I think the title "(easy)" is quite misleading :) Anyway, nice one. --ans(Francky)--> What a curious idea to submit a wrong code! ;-) Good job. Ok it's not very easy, but it's the easiest of my recent problems. Last edit: 2014-05-23 07:43:03

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