Solved by 26 users: WsemirZ, Vladimir_Sitnikov, Philip_PV, JohnJones_001, defrager, UdH-WiNGeR, MasterYoda, ilyakor, dan, DAV, Kuznetsov_S, Robert_Gerbicz, vdmedragon, kp, murphy, RAVEman, Norbert, mathematic, TTLovePP, fetetriste, ripatti, Dest, ZhanibekDATBAEV, Jacob, NIGHTFIT, mikelan.
UserDateAttemptTimeCMSC
Dest`20 jun 2010`C++400.154123
Robert_Gerbicz`25 may 2009`C300.53693
vdmedragon`27 jun 2009`C++4400.531257
vdmedragon`11 apr 2010`C++4700.571257
vdmedragon`02 jun 2009`C++1400.731082
JohnJones_001`26 may 2009`C++700.82813
NIGHTFIT`20 apr 2012`C++1200.881324
NIGHTFIT`06 mar 2012`C++900.901314
RAVEman`28 jul 2009`C++1201.031124
ZhanibekDATBAEV`21 jun 2010`C++2801.271025
Vladimir_Sitnikov`07 apr 2009`Ruby201.30167
ZhanibekDATBAEV`21 jun 2010`C++2701.351025
Robert_Gerbicz`25 may 2009`C++201.36669
Norbert`03 nov 2009`C1101.382088
Norbert`03 nov 2009`C1401.392066
defrager`08 apr 2009`C++1801.427487
 C++ 12 Java 6 Ruby 5 Haskell 4 C 3 Kylix 1
` >  >  >  >  >  >  >  >  >  > `

Irreducible polynomial

Time limit = 3 seconds

Memory limit = 10 Mb

Let us consider a ring of polynomials of single variable on GF(2). That is a ring of polynomials with coefficients modulo 2. It turns out some polynomials can be factorized into polynomials of lesser degree, while some are not.

For instance, x2+1 is reducible since x2+1 = x2+2x+1 = (x+1)(x+1). It is easy to show that x2+x+1 is irreducible.

The problem is to find the total number of all irreducible polynomials with degree equal to n (1 ≤ n ≤ 300'000).

Input Integer n (1 ≤ n ≤ 300'000)

Output Number of irreducible polynomials

 Input#1```2 ``` Output#1```1 ```
 Input#2```10 ``` Output#2```99 ```

Author:
Description and tests by Malyshev Egor
6 april 2009

 © acm.mipt DevGroupThe page was generated in 200ms