2229 - numere20

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

17

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>