Rezolvare PBinfo #1969

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)₈=digit(2+1+7+5+6)₈=25, întrucât c>8 procedeul continuă
• c=digit(25)₈=digit(2+5)₈=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.