Codeforces Round #716 (Div. 2) C.Product 1 Modulo N（裴蜀定理）

本文主要是介绍Codeforces Round #716 (Div. 2) C.Product 1 Modulo N（裴蜀定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：http://codeforces.com/contest/1514

Now you get Baby Ehab’s first words: “Given an integer nn, find the longest subsequence of [1,2,…,n−1] whose product is 11 modulo nn.” Please solve the problem.

A sequence bb is a subsequence of an array aa if bb can be obtained from aa by deleting some (possibly all) elements. The product of an empty subsequence is equal to 11.

Input
The only line contains the integer nn (2≤n≤1052≤n≤105).

Output
The first line should contain a single integer, the length of the longest subsequence.

The second line should contain the elements of the subsequence, in increasing order.

If there are multiple solutions, you can print any.

Examples

input

output

3
1 2 3

input

output

4
1 3 5 7

分析

如果我们选择了 a ，已经选入的数的乘积为 x ，那么 a ∗ x ≡ 1(mod n) ，所以 a 就是 n 的逆元，所以 gcd(a, n) = 1 ，也就是说选入的数必须是与 n 互质的数。
若乘积为 t ，那么我们得到 x mod n = t ，那么我们只要不加入 t 就可以得到 (x / t) mod n = 1 。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;vector<ll> ans;int main()
{ll n,tmp = 1;scanf("%lld",&n);for(int i=1;i<n;i++){ll x = 1ll*i;if(__gcd(x, n) == 1){ans.push_back(x);tmp = tmp * x % n;}}int flag = 0;for(int i=0;i<ans.size();i++){if(ans[i] == tmp){flag = i;break;}}printf("%d\n",ans.size()-(flag != 0));for(int i=0;i<ans.size();i++){if(i == flag && flag != 0) continue;printf("%lld ",ans[i]);}return 0;
}