<ПРЕД Задача:
СЛЕД>
Задачу решили 26 пользователей: 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.
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Неприводимые многочлены

Time limit = 3 секунды

Memory limit = 10 Mb

Рассмотрим кольцо многочленов одной переменной над GF(2). То есть многочленов, операции над коэффициентами которых производятся по модулю 2 Получается, что некоторые многочлены разложимы на многочлены меньших степеней (такие многочлены называют неприводимыми), а некоторые нет.

Например, x2+1 — приводим, т.к. x2+1 = x2+2x+1 = (x+1)(x+1), а x2+x+1 — неприводим.

Требуется найти общее количество неприводимых многочленов степени n (1 ≤ n ≤ 300'000).

Вход Натуральное число N ≤ 300'000

Выход Количество неприводимых многочленов

Вход#1
2
Выход#1
1

Вход#2
10
Выход#2
99

Автор:
Описание, тесты -- Малышев Егор
6 april 2009

<ПРЕД | Вернуться к списку задач | Искать сообщения в форуме | СЛЕД>


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

SW soft NIX
ID = 18.207.106.142