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

 © acm.mipt DevGroupThe page was generated in 190ms