from functools import reduce
from math import gcd


class ModInvError(Exception):
    pass


def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = egcd(b % a, a)
        return g, y - (b // a) * x, x


def modinv(b, n):
    g, x, _ = egcd(b, n)
    if g == 1:
        return x % n
    else:
        raise ModInvError()


def crack_unknown_increment(states, modulus, multiplier):
    increment = (states[1] - states[0] * multiplier) % modulus
    return modulus, multiplier, increment


def crack_unknown_multiplier(states, modulus):
    multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
    return crack_unknown_increment(states, modulus, multiplier)


def crack_unknown_modulus(states):
    diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
    zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
    modulus = abs(reduce(gcd, zeroes))
    return crack_unknown_multiplier(states, modulus)


def lcg_next(a, c, m, seed):
    return (a * seed + c) % m


def main():
    tries = 0

    while True:
        tries += 1
        data = list(map(int, input('Enter some numbers (~10): ').split()))
        try:
            m, a, c = crack_unknown_modulus(data)
            print('[+] hacked with {} tries m={}, a={}, c={}'.format(tries, m, a, c))
            num = data[-1]
            for i in range(10):
                num = lcg_next(a, c, m, num)
                print('[+] next number {}'.format(num))
        except ModInvError:
            pass
        else:
            break


if __name__ == '__main__':
    main()
