HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Unsorted > problem:


Sequence

Section problems

• Making Potions
• Santa Gifts
• Chessboard Pattern
• Galls village
• Sequence
• Bishops
• Polygons
• String manipulations
• Lawyers Council
• Math and Soldiers
• Many-coloured roads
• What about judges?
• Liars and Knights

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 3000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Автор: Кирилл Бутин, ПГУ.

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.

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

Output
Output a single number – the answer for the problem.

Input 1 Output 1
5
1
0

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

www.contester.ru