Vulnerable Kerbals (Codeforces 772C)
Tags: Math, number theory

You are given an integer m, and a list of n distinct integers between 0 and m - 1.You would like to construct a sequence satisfying the properties:  Each element is an integer between 0 and m - 1, inclusive.  All prefix products of the sequence modulo m are distinct.  No prefix product modulo m appears as an element of the input list.  The length of the sequence is maximized. Construct any sequence satisfying the properties above.

Input: The first line of input contains two integers n and m (0 ≤ n < m ≤ 200 000) — the number of forbidden prefix products and the modulus.If n is non-zero, the next line of input contains n distinct integers between 0 and m - 1, the forbidden prefix products. If n is zero, this line doesn't exist.

Output: On the first line, print the number k, denoting the length of your sequence.On the second line, print k space separated integers, denoting your sequence.

Note: For the first case, the prefix products of this sequence modulo m are [1, 2, 3, 4, 0].For the second case, the prefix products of this sequence modulo m are [3, 7, 4, 6, 8, 0].

Sample Inputs:
0 5

3 10
2 9 1

Sample Outputs:
5
1 2 4 3 0

6
3 9 2 9 8 0

Solution (Python):
import math

def gcdExtended(a, b):
    if a == 0:
        return (b, 0, 1)
    (gcd, x1, y1) = gcdExtended(b % a, a)
    x = y1 - b // a * x1
    y = x1
    return (gcd, x, y)

def rev_elem(x, m):
    return (gcdExtended(x, m)[1] % m + m) % m
(n, m) = map(int, input().split())
a = []
if n > 0:
    a = [int(i) for i in input().split()]
banned = [False] * (m + 5)
for i in a:
    banned[i] = True
cycle = [[] for i in range(m + 5)]
(d, dp, p) = ([], [], [])
for i in range(m):
    cycle[math.gcd(m, i)].append(i)
cycle = [[i for i in j if not banned[i]] for j in cycle]
d = [i for i in range(1, m + 1) if m % i == 0]
dp = [len(cycle[i]) for i in d]
p = [-1 for i in d]
(ans, lst) = (-1, -1)
for i in range(len(d)):
    if dp[i] > ans:
        (ans, lst) = (dp[i], i)
    for j in range(i + 1, len(d)):
        if d[j] % d[i] != 0 or dp[j] > dp[i] + len(cycle[d[j]]):
            continue
        dp[j] = dp[i] + len(cycle[d[j]])
        p[j] = i
print(ans)
(pos, dpos, pref) = ([], [], [])
cur = lst
while cur != -1:
    dpos.append(d[cur])
    cur = p[cur]
dpos.reverse()
for i in dpos:
    pref += cycle[i]
cur = 1
for i in pref:
    ad = 1
    if math.gcd(i, m) != math.gcd(cur, m):
        ad = cur * math.gcd(i, m) // math.gcd(cur, math.gcd(i, m)) // cur % m
    ncur = cur * ad % m
    ad *= i // math.gcd(ncur, m) * rev_elem(ncur // math.gcd(ncur, m), m // math.gcd(ncur, m))
    ad %= m
    cur = cur * ad % m
    pos.append(ad)
print(*pos)

Solution (Python):
maxn = 200500
g = [[] for i in range(maxn)]
dp = [0 for i in range(maxn)]
ban = [0 for i in range(maxn)]
nxt = [0 for i in range(maxn)]
m = 0

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return (a, x, y)
    (ret, x, y) = exgcd(b, a % b)
    tmp = x
    x = y
    y = tmp - int(a / b) * y
    return (ret, x, y)

def f(a, b):
    (r1, x, y) = exgcd(a, m)
    if b % r1 != 0:
        return -1
    x = (x + m) % m * int(b / r1) % m
    return x

def dfs(p):
    if dp[p] != 0:
        return
    res = 0
    for i in range(p * 2, m, p):
        if len(g[i]) > 0:
            dfs(i)
        if dp[i] > res:
            res = dp[i]
            nxt[p] = i
    if len(g[p]) > 0:
        res += len(g[p])
    dp[p] = res
(a, b) = input().split(' ')
n = int(a)
m = int(b)
if n > 0:
    lista = input().split(' ')
for i in range(1, n + 1):
    x = int(lista[i - 1])
    ban[x] = 1
for i in range(1, m):
    if ban[i] == 0:
        d = gcd(i, m)
        g[d].append(i)
dfs(1)
ban0 = 0
if ban[0] == ban0:
    ban0 = 1
print(dp[1] + ban0)
u = 1
x = 1
sec = ''
while u != 0:
    for i in range(0, len(g[u])):
        v = g[u][i]
        print(str(f(x, v)) + ' ', end=' ')
        x = v
    u = nxt[u]
if ban0 == 1:
    print('0')

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

def ext_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    (gcd, x, y) = ext_gcd(b, a % b)
    return (gcd, y, x - a // b * y)

def mod_inv(a, p):
    (gcd, x, y) = ext_gcd(a, p)
    return x % p

def main():
    (n, m) = MII()
    forbidden = [0] * m
    for x in MII():
        forbidden[x] = 1
    gcds = [[] for _ in range(m + 1)]
    for i in range(m):
        if not forbidden[i]:
            gcds[math.gcd(i, m)].append(i)
    dp = [0] * (m + 1)
    to = [-1] * (m + 1)
    for i in range(m, 0, -1):
        for j in range(2 * i, m + 1, i):
            if dp[j] > dp[i]:
                dp[i] = dp[j]
                to[i] = j
        dp[i] += len(gcds[i])
    ans = []
    cur = dp.index(max(dp))
    while cur != -1:
        ans.extend(gcds[cur])
        cur = to[cur]
    print(len(ans))
    res = [ans[0]]
    for i in range(1, len(ans)):
        (a, b, p) = (ans[i - 1], ans[i], m)
        x = math.gcd(a, p)
        a //= x
        b //= x
        p //= x
        res.append(b * mod_inv(a, p) % p)
    print(*res)
    return
t = 1
for _ in range(t):
    main()