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

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