GF2 - Irreducible polynomials over GF2

Find the number of degree n irreducible polynomials over GF(2). For example: for n=1 there are two such polynomials: x and x+1. For n=2 there is only one: x2+x+1. Note that in R[x] the polynomials x2+1 is irreducible, but not over GF(2), because x2+1 = (x+1)*(x+1)

Input

A single positive integer n, where n < 500000.

Output

Output the answer for n.

Example

Input:
201

Output:
15989433276208858463104100421305100522608250813995004946218
Input:
1

Output:
2
Input:
2

Output:
1
Input:
3

Output:
2

Added by:Robert Gerbicz
Date:2009-05-25
Time limit:0.100s-1s
Source limit:4096B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:classic problem, own input

hide comments
2020-10-27 15:59:19 David
For max input, using Java, result generated in 0 ms and printed in 160 ms. TLE here.
2010-04-11 04:09:51 ~!(*(@*!@^&
C++ 4.3.2 is faster than 4.0.0.2
2009-10-15 06:59:16 numerix
Python isn't too slow for that problem. Multiplication in python IS fast (Karatsuba). The only problem is the output of the large numbers (> 150000 digits), which is veeeery slow in python. So to get AC you have to do some optimizing on that - and use python 2.5 instead of 2.6!

Last edit: 2009-10-19 06:02:38
2009-08-27 17:27:28 Lukas Polacek
I have learned Haskell for this problem :) If you know Python well you can do this task in Haskell under one hour.
2009-05-31 10:18:16 Robert Gerbicz
That means your solution is slow.
2009-05-31 07:33:01 thomas anderson
My code is running in 0.01s without print answer, but get TLE when print the output using fputs. How that is possible?
// edited, your formula is good.

Last edit: 2009-06-04 16:16:22
2009-05-26 08:33:06 Robert Gerbicz
OK, raised the source limit to 4KB. Try to submit your code!
2009-05-26 08:31:50 Robert Gerbicz
"why the source limit is so tight?"
It is only indicating that you don't need to implement fft or even karatsuba method for multiplication in c/c++. Using grammar school multiplication is enough. Or use another language where there is a big integer library and multiplication is "fast".

Last edit: 2009-05-26 07:48:36
2009-05-26 08:31:50 ~!(*(@*!@^&
why the source limit is so tight?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.