|Online MIPT programming contest||РУССКИЙ|
Time limit = 3 seconds
Memory limit = 10 MbLet 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
Description and tests by Malyshev Egor
6 april 2009
© acm.mipt DevGroup
The page was generated in 170ms