3045 - Pro 3

Se consideră 3 progresii aritmetice de numere naturale nenule. Notăm cu Pi, 1 ≤ i ≤ 3, mulțimile formate cu elementele progresiei i. Fie P = P1  P2  P3 reuniunea mulțimilor P1, P2, P3.

Cerința

Să se determine cardinalul mulțimii P.

Date de intrare

Fișierul de intrare input.txt conține 3 linii. Pe linia i, 1 ≤ i ≤ 3 se vor găsi câte trei numere naturale ai, ri, ni, separate prin câte un spațiu, ce reprezintă în această ordine primul termen, rația și numărul de termeni ai progresiei Pi.

Date de ieșire

Fișierul de ieșire output.txt va conține pe prima linie cardinalul mulțimii P.

Exemplu

input.txt:

2 2 10

3 4 8

1 3 12

output.txt:

24

Explicație:

Prima progresie are primul termen 2, rația 2 și 10 termeni.

A doua progresie are primul termen 3, rația 4 și 8 termeni.

A treia progresie are primul termen 1, rația 3 și 12 termeni.

Așadar:

P1 = {2, 4, 6, 8, 10, 12, 14, 16, 18, 20}

P2 = {3, 7, 11, 15, 19, 23, 27, 31}

P3 = {1, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34}

Reuniunea termenilor celor trei progresii este mulțimea

P = {1, 2, 3, 4, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 18, 19, 20, 22, 23, 25, 27, 28, 31, 34} și cardinalul mulțimii P este 24.

Rezolvare

class Progresie:
    def __init__(self, first, ratio, n):
        self.first = first
        self.ratio = ratio
        self.n = n

def read():
    with open("input.txt", "r") as f:
        x_values = list(map(int, f.readline().split()))
        y_values = list(map(int, f.readline().split()))
        z_values = list(map(int, f.readline().split()))
    
    return Progresie(*x_values), Progresie(*y_values), Progresie(*z_values)

def cmmdc(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def cmmmc(a, b):
    return a * b // cmmdc(a, b)

def calc(a, b):
    Maxa = a.first + a.ratio * (a.n - 1)
    Maxb = b.first + b.ratio * (b.n - 1)
    Min = min(Maxa, Maxb)
    for i in range(int(1e6)):
        nr = a.first + i * a.ratio
        if nr >= b.first and nr <= Min and (nr - b.first) % b.ratio == 0:
            return Progresie(nr, cmmmc(a.ratio, b.ratio), (Min - nr) // cmmmc(a.ratio, b.ratio) + 1)
    return Progresie(0, 0, 0)

def solve(x, y, z):
    xy = calc(x, y)
    xz = calc(x, z)
    yz = calc(y, z)
    xyz = calc(xy, z)
    return x.n + y.n + z.n - xy.n - xz.n - yz.n + xyz.n

def output(rez):
    with open("output.txt", "w") as g:
        g.write(str(rez))

if __name__ == "__main__":
    x, y, z = read()
    rez = solve(x, y, z)
    output(rez)