Pentru obținerea Pietrei Filosofale, un alchimist a preparat un elixir folosind un creuzet de capacitate C, în care a turnat picături de metal topit, într-o ordine bine stabilită, în N etape. Numărul de picături turnate într-o etapă este cuprins între 0 și C-1, iar procesul începe când în creuzet s-a turnat prima picătură (în prima etapă numărul de picături turnate este nenul). Picăturile se adună în creuzet una câte una şi, de fiecare dată când acesta se umple complet, alchimistul rosteşte o formulă magică, provocând transformarea întregului conţinut într-o singură picătură, apoi continuă procesul. O rețetă de obținere a elixirului se exprimă printr-un șir de N numere, reprezentând numărul de picături turnate în cele N etape.

De exemplu, aplicând rețeta 5 6 1 0, cu un creuzet de capacitate C=7, în cele N=4 etape procesul este:

etapa 1: se toarnă 5 picături;
etapa a 2-a: se toarnă 6 picături, astfel: după primele 2 picături se umple creuzetul (5+2=7) și deci se rosteşte formula magică, în creuzet rămânând o picătură; se continuă cu celelalte 4 picături; la finalul etapei în creuzet sunt 5 picături (1+4=5);
etapa a 3-a: se toarnă o picătură; la finalul etapei în creuzet sunt 6 picături (5+1=6);
etapa a 4-a: se toarnă 0 picături; după ultima etapă creuzetul conține 6 picături (6+0=6).

O rețetă care corespunde Pietrei Filosofale trebuie să conducă, la finalul aplicării ei, la obținerea unei singure picături, chintesența metalelor amestecate. Bineînțeles, sunt mai multe astfel de rețete.

Fiind un tip responsabil, alchimistul a lăsat posterității un set de tratate, care cuprind toate aceste rețete. El a scris pe fiecare pagină câte o rețetă, astfel încât niciuna să nu se repete în cadrul întregii lucrări. Pe vremea aceea erau meșteri pricepuți, care fabricau tratate de dimensiuni corespunzătoare, încât fiecare pagină să poată cuprinde o rețetă ca a noastră, oricât de lungă ar fi ea. Fiecare tratat are P pagini și doar după ce completează toate cele P pagini ale unui tratat, alchimistul începe un nou tratat.

Cerinţă:

Se cere numărul de rețete publicate în ultimul tratat.

Date de intrare

Fișierul de intrare magic1.in conține pe prima linie, în această ordine, numerele naturale C, N, P, separate prin câte un spațiu și având semnificația din enunț.

Date de ieșire

Fișierul de ieșire magic1.out va conține un număr natural reprezentând numărul de rețete publicate în ultimul tratat.

Restricții și precizări

1<C≤10^7; 2≤N≤10^7; 1≤P≤10^7, numere naturale;
pentru 30% dintre teste, C≤10 și N<10, iar pentru 70% dintre teste, N≤10^4.

Exemplu

magic1.in

4 2 3

magic1.out

Explicație

Creuzetul are capacitatea C=4, sunt N=2 etape de aplicare a fiecărei rețete, tratatele au câte P=3 pagini. Rețetele aplicate în două etape, în urma fiecărui astfel de proces rămânând în creuzet câte o singură picătură, sunt: 1 0; 1 3; 3 1; 2 2. Pentru acestea sunt necesare două tratate, primul conținând trei rețete, iar al doilea (ultimul) o singură rețetă.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Magic1:

#include <iostream>
#include <fstream>

using namespace std;
ifstream in("magic1.in");
ofstream out("magic1.out");
long long C;
long N,P;

int main()
{
    long i;
    long long nr;
    in>>C>>N>>P;

    N--;
    nr=1;
    while(N!=0){
        if(N%2==1)
        {
            nr=(nr*C)%P;
            if(nr==0)
                nr=P;
        }
        C=(C*C)%P;
        if(C==0)
            C=P;
        N/=2;
    }
    out<<nr;

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1223 Magic1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1223 Magic1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1223 Magic1