<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.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

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 = 54.224.164.166