lottery.py

N = 21370120468385321072796737813133108220219513181325112990447360992546500389694548252269265893063462093795745311003079259032259284817724142967307419548692230509748974136162778121191352870524136742515751412463885987947887383533209373995633172270747839462573684451579482448711557255544051877926568399192278180628779826942841771371089102475387280427210008316736688671049781437332916605849326863448921860142397187007392504097718172738021889119053248986852465983882536423905574279750120180701449864682876951406958864741734242052818961621523746486255350414607432255689673361596949675438577686588496722927000403138432462363899


def main():
    # key.txtは当選者決定後に公開します
    with open('key.txt') as f:
        a = f.readlines()
        p = int(a[0])
        q = int(a[1])
        d = int(a[2])
    assert p * q == N
    assert d * 65537 % ((p - 1) * (q - 1)) == 1
    m = pow(1 << 1000, d, N)

    # users.txtは抽選対象者のIDを改行区切りで入れたもの
    with open('users.txt', 'rb') as f:
        users = sorted(x for x in f.read().split(b'\n') if x != b'')

    h = 5381
    for s in users:
        for c in s:
            h = (h * 33 + c) % (1 << 64)

    x = (m + h) % (1 << 64)
    for _ in range(10):
        x = (x ^ (x << 13)) % (1 << 64)
        x = (x ^ (x >> 7)) % (1 << 64)
        x = (x ^ (x << 17)) % (1 << 64)
        y = x % len(users)
        print(users[y].decode())
        del users[y]


main()