Chernel

chernel

== include(page="template/taskheader" task_id="chernel") ==

Chernel a renuntat la afaceri si s-a apucat de matematica. De aceasta data, el studiaza niste siruri mai speciale. Chernel porneste de la un sir de $N$ numere naturale $a{~1~} a{~2~} ... a{~N~}$, pe care aplica transformari succesive care schimba un sir de $X$ elemente $a{~1~} a{~2~} ... a{~X~}$ in sirul de $X-1$ elemente $a{~1~}+a{~2~} a{~2~}+a{~3~} ... a{~X-1~}+a{~X~}$. Chernel repeta aceasta operatie pana cand ramane cu un singur element. De aici obtine $numarul caracteristic$ al sirului, ca fiind restul impartirii aceslui ultim element ramas la un numar natural $M$.
 
Chernel observa ca valorile unor elemente din sirul initial nu influenteaza $numarul caracteristic$ al sirului, altfel spus oricare ar fi valoarea acestora, $numarul caracteristic$ ramane acelasi.
 
Pentru $N$ si $M$ date, ajutati-l pe Chernel sa afle cate astfel de valori exista in sirul initial.

Poveste si cerinta...

h2. Date de intrare

Pe prima linie a fisierului de intrare $chernel.in$ se gasesc cele doua numere naturale $N$ si $M$.

...

h2. Date de iesire

Pe prima linie a fisierului de iesire $chernel.out$ se va gasi un singur numar natural, reprezentand numarul de elemente din sirul initial a caror valoare nu influenteaza $numarul caracteristic$ al sirului.

...

h2. Restrictii

* $1 ≤ N ≤ 100.000$
* $1 ≤ M ≤ 1.000.000.000$

... ≤ ...

h2. Exemplu
table(example). |_. chernel.in |_. chernel.out |

| 3 2
| 1

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicatie

Fie sirul initial $a{~1~} a{~2~} a{~3~}$. Acesta se transforma in $a{~1~}+a{~2~} a{~2~}+a{~3~}$ apoi in $a{~1~}+2*a{~2~}+a{~3~}$. Pentru $M = 2$, singura valoare a sirului initial care nu influenteaza $numarul caracteristic$ este $a{~2~}$

...

== include(page="template/taskfooter" task_id="chernel") ==

1495