<PREV Problem:
NEXT>
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
Dest20 jun 2010C++400.154123 
Robert_Gerbicz25 may 2009C300.53693 
vdmedragon27 jun 2009C++4400.531257 
vdmedragon11 apr 2010C++4700.571257 
vdmedragon02 jun 2009C++1400.731082 
JohnJones_00126 may 2009C++700.82813 
NIGHTFIT20 apr 2012C++1200.881324 
NIGHTFIT06 mar 2012C++900.901314 
RAVEman28 jul 2009C++1201.031124 
ZhanibekDATBAEV21 jun 2010C++2801.271025 
Vladimir_Sitnikov07 apr 2009Ruby201.30167 
ZhanibekDATBAEV21 jun 2010C++2701.351025 
Robert_Gerbicz25 may 2009C++201.36669 
Norbert03 nov 2009C1101.382088 
Norbert03 nov 2009C1401.392066 
defrager08 apr 2009C++1801.427487 
Languages
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

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 18.210.24.208