El Judge
| Online MIPT programming contest | РУССКИЙ |
| <PREV Problem: | NEXT> |
< |
|---|
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#12 |
Output#11 |
Input#210 |
Output#299 |
Author:
Description and tests by Malyshev Egor
6 april 2009
© acm.mipt DevGroup The page was generated in 170ms |
