lottery.py

N = 25896857786810726855022146374999541490792629321172163039866685924034802352508239010428011811841143590926478852343668890103153910876024186934800979843667464190096499569252663287804867991100682962514603299368689877860870128394679392568108056380727022178661467531416990286422108322876117761063136728468435862763811783701481689598219540748281494694371097905346786534941068314677820680458439354610900686878182430198753748721508118302843973116198209031034813959191337481599407937778068187062316723100355984120098439664529734744694148037671791836672507247047927690045312545517902865173349636564002717007596572606485173708547


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