RebecaBud: Pagină nouă: == Enunt == 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ă re...

2024-06-03T16:23:06Z

Pagină nouă: == Enunt == 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ă re...

New page

== Enunt ==
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
== Exemplul 1 ==
; 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.
<br>

== Rezolvare ==
<syntaxhighlight lang="python" line>
def is_prime(n):
if n <= 1:
return False
if n <= 3:
return True
if n % 2 == 0 or n % 3 == 0:
return False
i = 5
while i * i <= n:
if n % i == 0 or n % (i + 2) == 0:
return False
i += 6
return True

def digit_sum(num, base):
result = sum(int(digit, base=base) for digit in str(num))
while result >= base:
result = sum(int(digit, base=base) for digit in str(result))
return result

def prime_in_interval(x, y):
for num in range(x, y+1):
if is_prime(num):
return num
return None

def minimum_base(prime):
return min(prime, 8)

def control_digit(prime, base):
return digit_sum(prime, base)

def primes_with_control_digit(x, y, base, control_digit):
count = 0
for num in range(x, y+1):
if is_prime(num):
if digit_sum(num, base) == control_digit:
count += 1
return count

def main():
with open("pdigit.in", "r") as fin:
x, y = map(int, fin.readline().split())

prime = prime_in_interval(x, y)
base = minimum_base(prime)
control = control_digit(prime, base)
count = primes_with_control_digit(x, y, base, control)

with open("pdigit.out", "w") as fout:
fout.write(f"{prime}\n")
fout.write(f"{base}\n")
fout.write(f"{control}\n")
fout.write(f"{count}\n")

if __name__ == "__main__":
main()

</syntaxhighlight>

1969 - P Digit - Revision history