Enunt

Ionel are de rezolvat mai multe probleme de divizibilitate. Unele dintre ele îi cer să afle câte numere au anumite proprietăţi. Vă rugăm să-l ajutaţi să termine tema mai repede.

Cerința

Scrieţi un program care citeşte un număr natural n şi două numere prime u şi v mai mici decât 10 şi determină câte numere naturale mai mici sau egale cu n au proprietatea că nu sunt divizibile nici cu u, nici cu v.

Date de intrare

Fișierul de intrare numere20.in conţine pe prima linie numărul natural n şi cifrele u şi v, separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire numere20.out va conţine o singură linie pe care va fi scris numărul de numere naturale mai mici sau egale cu n care nu sunt divizibile nici cu u, nici cu v. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

Numărul natural n are cel mult 100 de cifre

Exemplul 1:

numere20.in

30  3  7

numere20.out

Explicație

Numerele care au proprietatea din enunţ sunt: 1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20, 22, 23, 25, 26, 29.

Exemplul 2:

numere20.in

30  3  7

numere20.out

Datele nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3"> LG = 1001

def Set(a, x):

   n = len(x)
   a[0] = n
   for i in range(1, n + 1):
       a[i] = int(x[n - i])

def copie(A, B):

   A[:LG] = B[:LG]

def scrie(a):

   with open("numere20OUT.txt", "w") as g:
       for i in range(a[0], 0, -1):
           g.write(str(a[i]))
       g.write('\n')

def verifica_restrictii(n, u, v):

   if n[0] > 100 or u > 100 or v > 100:
       with open("numere20OUT.txt", "w") as g:
           g.write("Datele nu corespund restrictiilor impuse\n")
       return False
   return True

def suma(A, B, C):

   r, s = 0, 0
   C[:LG] = A[:LG]
   if A[0] > B[0]:
       C[0] = A[0]
   else:
       C[0] = B[0]
   i = 1
   while i <= B[0]:
       s = C[i] + B[i] + r
       r = s // 10
       C[i] = s % 10
       i += 1
   while r:
       s = C[i] + r
       r = s // 10
       C[i] = s % 10
       i += 1
   if i - 1 > C[0]:
       C[0] += 1

def dif(A, B, C):

   C[:LG] = A[:LG]
   i = 1
   while i <= C[0]:
       if C[i] >= B[i]:
           C[i] -= B[i]
       else:
           j = i + 1
           while C[j] == 0:
               C[j] = 9
               j += 1
           C[j] -= 1
           C[i] += 10 - B[i]
       i += 1
   i = C[0]
   while i > 1 and C[i] == 0:
       i -= 1
   C[0] = i

def divide_mare_mic(a, b, c):

   x, i, j = 0, a[0], 0
   y = [0] * LG
   while x < b and i > 0:
       x = x * 10 + a[i]
       i -= 1
   x = x // 10
   i += 1
   while i > 0:
       x = x * 10 + a[i]
       y[j] = x // b
       x = x % b
       i -= 1
       j += 1
   if j == 0:
       c[0] = 1
       c[1] = 0
   else:
       c[0] = j
       for i, k in enumerate(range(j - 1, -1, -1), start=1):
           c[i] = y[k]

def main():

   nn, u, v = f.readline().split()
   u, v = int(u), int(v)
   n, nr1, nr2, nr3, nr4, nr5, nr = [0] * LG, [0] * LG, [0] * LG, [0] * LG, [0] * LG, [0] * LG, [0] * LG
   Set(n, nn)

   if not verifica_restrictii(n, u, v):
       return

   divide_mare_mic(n, u, nr1)
   divide_mare_mic(n, v, nr2)
   suma(nr1, nr2, nr3)
   divide_mare_mic(n, u * v, nr4)
   dif(nr3, nr4, nr5)
   dif(n, nr5, nr)
   scrie(nr)

if __name__ == "__main__":

   with open("numere20IN.txt", "r") as f:
       main()

</syntaxhighlight>