ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Сборники > Kovrov IT 2010 > задача:

G. Sequence

Задачи сборника

• Задача 7
• A. Провайдеры
• B. Primes
• C. Bishops
• D. Unusual Lottery
• E. Polygons
• F. Liars and Knights
• G. Sequence
• H. Coins
• I. Galls village
• J. String manipulations

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 3000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Автор: Кирилл Бутин, ПГУ.

You are given an infinite sequence of integers:
A0 = 0
Ai = ( Ai-1 + q ) mod p, for i > 0

Where p is a prime number, a mod p is reminder of division a by p.

Your task is to count how many integers in the range [0..p-1] are not included in this sequence. Notice that p can be very large.

The first line contains one prime integer p.
The second line contains one integer q. (0 ≤ qp ≤ 10100).

Output a single number – the answer for the problem.

Input 1 Output 1

Для отправки решений необходимо выполнить вход.