Product 1 Modulo N

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
 
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
 
int main() {
	int n;
	cin >> n;
	vector<ll> coprimes;
	/*
	 * This array stores all of the numbers
	 * which are less than n and are coprime with n.
	 */
	for (int i = 1; i < n; i++) {
		// A number is coprime with n if gcd(n, i) = 1
		if (gcd(n, i) == 1) { coprimes.push_back(i); }
	}
 
	/*
	 * The longest subsequence whose product is 1 modulo n
	 * is the longest subarray of coprimes with a product
	 * of 1 modulo n.
	 */
 
	int number_of_coprimes = coprimes.size();
	vector<ll> prefix_mod(number_of_coprimes);
	prefix_mod[0] = 1;
	/*
	 * We can take the modulo prefix to check the modulus
	 * of the first k coprimes, where k is the end of the
	 * subarray.
	 */
	for (int i = 1; i < number_of_coprimes; i++) {
		prefix_mod[i] = (prefix_mod[i - 1] * coprimes[i]) % n;
	}
	int length_of_longest_subarray = 1;
	for (int i = 0; i < number_of_coprimes; i++) {
		/*
		 * If a given subarray has a product of
		 * 1 modulo n, update the length of the
		 * longest subsequence with product 1
		 * modulo n.
		 */
		if (prefix_mod[i] == 1) { length_of_longest_subarray = i + 1; }
	}
	cout << length_of_longest_subarray << endl;
	for (int i = 0; i < length_of_longest_subarray; i++) { cout << coprimes[i] << " "; }
	cout << endl;
}

import java.io.*;
import java.util.*;
 
public class Prod1ModN {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
 
		ArrayList<Long> coprimes = new ArrayList<>();
 
		/*
		 * This array stores all of the numbers
		 * which are less than n and are coprime with n.
		 */
		for (int i = 1; i < n; i++) {
			// A number is coprime with n if gcd(n, i) = 1
			if (gcd(n, i) == 1) { coprimes.add((long)i); }
		}
 
		/*
		 * The longest subsequence whose product is 1 modulo n
		 * is the longest subarray of coprimes with a product
		 * of 1 modulo n.
		 */
 
		int numberOfCoprimes = coprimes.size();
		long[] prefixMod = new long[numberOfCoprimes];
		prefixMod[0] = 1;
 
		/*
		 * We can take the modulo prefix to check the modulus
		 * of the first k coprimes, where k is the end of the
		 * subarray.
		 */
		for (int i = 1; i < numberOfCoprimes; i++) {
			prefixMod[i] = (prefixMod[i - 1] * coprimes.get(i)) % n;
		}
 
		int lengthOfLongestSubarray = 1;
		for (int i = 0; i < numberOfCoprimes; i++) {
			/*
			 * If a given subarray has a product of
			 * 1 modulo n, update the length of the
			 * longest subsequence with product 1
			 * modulo n.
			 */
			if (prefixMod[i] == 1) { lengthOfLongestSubarray = i + 1; }
		}
 
		io.println(lengthOfLongestSubarray);
 
		for (int i = 0; i < lengthOfLongestSubarray; i++) {
			io.print(coprimes.get(i) + " ");
		}
		io.println();
 
		io.close();
	}
 
	public static long gcd(long a, long b) {
		if (b == 0) { return a; }
		return gcd(b, a % b);
	}
 
	// CodeSnip{Kattio}
}

import math
 
n = int(input())
coprimes = []
 
"""
This array stores all of the numbers
which are less than n and are coprime with n.
"""
 
for i in range(1, n):
	if math.gcd(n, i) == 1:  # A number is coprime with n if gcd(n, i) == 1
		coprimes.append(i)
 
 
"""
The longest subsequence whose product is 1 modulo n
is the longest subarray of coprimes with a product
of 1 modulo n.
"""
number_of_coprimes = len(coprimes)
prefix_mod = [0] * number_of_coprimes
prefix_mod[0] = 1
 
"""
We can take the modulo prefix to check the modulus
of the first k coprimes, where k is the end of the
subarray.
"""
for i in range(1, number_of_coprimes):
	prefix_mod[i] = (prefix_mod[i - 1] * coprimes[i]) % n
 
length_of_longest_subarray = 1
for i in range(number_of_coprimes):
	"""
	If a given subarray has a product of
	1 modulo n, update the length of the
	longest subsequence with product 1
	modulo n.
	"""
	if prefix_mod[i] == 1:
		length_of_longest_subarray = i + 1
 
print(length_of_longest_subarray)
for i in range(length_of_longest_subarray):
	print(coprimes[i], end=" ")