Cerința

A venit primăvara și a început sezonul de concursuri pentru porumbei. La un concurs fiecare participant trebuie să trimită câte doi porumbei. Fiecare porumbel are ataşat pe picior un inel care conţine un număr. Într-o noapte, înainte de un concurs, Tavi, un mare pasionat de porumbei, are un vis în care o zână bună îi spune codurile celor doi porumbei pe care, dacă îi va trimite, va câştiga concursul. Cum Tavi este un mare uituc, dimineaţa îşi mai aminteşte doar prima parte a visului în care zâna îi spune 2 numere a şi n. El îşi mai aminteşte că numerele X şi Y (pe care le-a uitat) de pe inelele porumbeilor sunt puse în aşa fel încât rezultatul a^X – a^Y să fie divizibil cu n. X și Y sunt numerele de pe inelele porumbeilor pe care îi va trimite la concurs.

Dându-se doua numere a şi n, să se afişeze cele două numere X şi Y cu Y minim.

Date de intrare

Fișerul porumbei.in are pe prima linie numerele a și n, separate printr-un spațiu.

Date de ieșire

Fișierul porumbei.out conține două numere naturale distincte, în ordine crescătoare și separate printr-un spațiu, ce reprezintă valorile minime ale lui X și Y astfel încât rezultatul a^X – a^Y să fie divizibil cu n.

Restricții și precizări

• 2 ≤ n ≤ 2.000.000
• 2 ≤ a ≤ 2.000.000
• 0 ≤ X < Y

Exemplu

porumbei.in

4 10

porumbei.out

1 3

Explicație

4¹=4
4³=64
4-64=-60 care este divizibil cu 10, iar valorile pentru X și Y sunt minime.

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 porumbei:

#include <iostream>
#include <fstream>
using namespace std;
ifstream f("porumbei.in");
ofstream g("porumbei.out");
char v[262145]; /// vectorul in care vom marca resturile gasite
long long m,n,a,x,r,p,q,r1,i;
int main()
{
    f>>m>>n;
    v[1/8]=v[1/8] | 1<<(1%8); /// (m^0)%n=1, deci marcam restul 1 ca intalnit

    a=1;
    r=1;
    while(1)
    {
        r=(r*m)%n;
        if((v[r/8] & (1<<(r%8)))!=0) /// daca bitul pe care ar trebui sa retinem restul e deja setat
        {
            q=a; /// inseamna ca inainte a mai fost un rest egal cu r, deci ne oprim
            break;  /// l-am gasit pe q asa ca ne oprim
        }
        else
            v[r/8]=v[r/8] | (1<<(r%8));
        a++;
    }
    if(r==1)
        p=0;
    else
        {
            r1=1;
            for(i=1;i<q;i++)
            {
                r1=(r1*m)%n;
                if(r1==r)
                {
                    p=i;
                    break;
                }
            }
        }
    g<<p<<" "<<q;
    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 #2059 porumbei

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2059 porumbei 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 #2059 porumbei