# PBinfo #2059 – porumbei – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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  aX – aY 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 aX – aY  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
41=4
43=64
4-64=-60 care este divizibil cu 10, iar valorile pentru X și Y sunt minime.

## Cod sursă C++

```cpp
#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;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/2059)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/2059/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-2059/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)