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
hide comments
|
David:
2020-10-27 15:59:19
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 |
|
numerix:
2009-10-15 06:59:16
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 |
|
Lukas Polacek:
2009-08-27 17:27:28
I have learned Haskell for this problem :) If you know Python well you can do this task in Haskell under one hour. |
|
Robert Gerbicz:
2009-05-31 10:18:16
That means your solution is slow. |
|
thomas anderson:
2009-05-31 07:33:01
My code is running in 0.01s without print answer, but get TLE when print the output using fputs. How that is possible?
|
|
|
Robert Gerbicz:
2009-05-26 08:33:06
OK, raised the source limit to 4KB. Try to submit your code! |
|
|
Robert Gerbicz:
2009-05-26 08:31:50
"why the source limit is so tight?"
|
|
|
~!(*(@*!@^&:
2009-05-26 08:31:50
why the source limit is so tight? |
| 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 |
RSS