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 mult100
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
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()