← 返回题目列表

Codeforces · 1514/C

C. 产品 1 模 N

中文机器翻译题面 查看原题

现在你会听到 Baby Ehab 的第一句话:“给定一个整数 $$$n$$$,找到 $$$[1,2, \ldots, n-1]$$$ 的最长子序列,其乘积为 $$$1$$$ 模 $$$n$$$。”请解决问题。

如果可以通过删除一些(可能是全部)元素从 $$$a$$$ 获得 $$$b$$$,则序列 $$$b$$$ 是数组 $$$a$$$ 的子序列。空子序列的乘积等于$$$1$$$。

输入

唯一一行包含整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。

输出

第一行应包含一个整数,即最长子序列的长度。

第二行应包含子序列的元素,按升序排列。

如果有多个解决方案,您可以打印任意一个。

示例

输入 #1

5

输出 #1

3
1 2 3

输入 #2

8

输出 #2

4
1 3 5 7

注意

在第一个示例中,元素的乘积是 $$$6$$$,它与 $$$1$$$ 模 $$$5$$$ 一致。唯一较长的子序列是 $$$[1,2,3,4]$$$。其乘积为 $$$24$$$,与 $$$4$$$ 模 $$$5$$$ 一致。因此,答案是$$$[1,2,3]$$$。