# PBinfo #1969 – pdigit – Rezolvare C++

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

## Enunț

Fie a un număr natural scris în baza 10. Notăm cu b, baza minimă în care poate fi scris a. Astfel, dacă a=21756, atunci baza minimă în care acesta poate fi scris este b=8. 

Definim cifra de control a numărului a scris în baza b, notată cu c=digit(a)b, ca fiind numărul de o cifră obținut prin adunarea în baza b a cifrelor numărului a. Dacă rezultatul obținut este de o cifră, atunci acesta reprezintă valoarea lui c, dacă nu, se aplică repetat asupra rezultatului procedeul de însumare a cifrelor în baza b până când se obține o cifră. 

De exemplu: 


c=digit(21756)8=digit(2+1+7+5+6)8=25, întrucât c>8 procedeul continuă
c=digit(25)8=digit(2+5)8=7.

Cerința
Se consideră un interval închis [x,y]. Să se determine:


a – primul număr prim mai mare sau egal ca x
b – baza minimă în care poate fi scris numărul prim a
c – cifra de control a numărului prim a
n – numărul de numere prime din  intervalul [x,y] ce pot fi scrise în baza b și au cifra de control egală cu c.

Date de intrare
Fișierul de intrare pdigit.in conține pe o singură linie două valori natural x și y cu semnificația din enunț.

Date de ieșire
Fișierul de ieșire pdigit.out va conține patru valori naturale a, b, c și n, scrise fiecare pe câte o linie, valori ce reprezintă în ordine: primul număr prim strict mai mare sau egal ca x, baza minimă în care poate fi scris numărul prim a, cifra de control a numărului prim a,  numărul de numere prime scrise în baza b din  intervalul [x,y] care au cifra de control egală cu c.

Restricții și precizări

1 ≤ x ≤ y ≤ 5000000
intervalul [x,y] conține cel puțin un număr prim
rezolvarea  primei cerințe asigură 10% din punctaj
rezolvarea cerinței a doua asigură 10% din punctaj
rezolvarea cerinței a treia asigură 20% din punctaj
Rezolvarea ultimei cerințe asigură 60% din punctaj

Exemplu:
pdigit.in

15 75
pdigit.out

17
8
1
3 
Explicație
Primul număr prim din interval este 17. Baza minimă în care poate fi scris numărul prim este 8.
Cifra de contro a numărului prim este 1. Sunt 3 numere prime în intervalul dat ce pot fi scrise în baza 8, și au cifra de control egală cu 1: 17, 53, 71.

## Cod sursă C++

```cpp
/*
	Solutie 100 p cu ciur
	prof. Eugen Nodea
*/
# include <fstream>
# include <bitset>
# define N_Max 5000050
using namespace std;
ifstream f("pdigit.in");
ofstream g("pdigit.out");
bitset <N_Max+1> ciur;
int p[360001];
int s, k, n, c, i, a, b, nr, j, m, x, y, z;
void ciurerathos(int N)
{
    int i, j, M;
    p[1] = 1; N += 50;
    for(i=2; i<=N; ++i){
        if(ciur[i] == 0){
            p[++nr] = i; M = N / i;
            for(j=2; j<=M; ++j)
                ciur[i*j] = 1;
        }
    }
}
int cifracontrol(int a, int b)
{
    int z = a, s, P, x;
    while (z >= b) {
        ///calculam suma
        s = 0;
        while(z > 0){
            if (z % 10 >= b) return -1;
            s += z % 10;
            z /= 10;
        }
        ///trec numarul in baza b
        P = 1; x = 0;
        while(s>0) {
            x += (s % b) * P;
            P *= 10;
            s /= b;
        }
        z = x;
    }
    return z;
}
int main()
{
    f >> x >> y;
    ciurerathos( y );
    ///caut primul numar prim care are cifra de control = c >=a
    i = 1; j = nr;
    while(i <= j) {
        m = (i + j) >> 1;
        if (x <= p[m]) j = m - 1;
        		  else i = m + 1;
    }
    a = p[j + 1];
    g << a << "\n";
    ///determin baza b
    b = 0; z = a;
    while(z > 0){
        c = z % 10;
        if (c > b) b = c;
        z /= 10;
    }
    ++b;
    g << b << "\n";
    ///determin cifra de control
    c = cifracontrol(a, b);
    g << c << "\n";
    ///determin numerele prime din intervalul [x,y]
    i = j+2; k = 1;
    while (p[i] <= y) {
        if (cifracontrol(p[i], b) == c) ++k;
        ++i;
    }
    g << k << "\n";
    return 0;
}
```

## Resurse

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