Now you get Baby Ehab's first words: "Given an integer nn, find the longest subsequence of [1,2,…,n−1][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.
#include<bits/stdc++.h> #define ll long long int using namespace std; const ll mod = 1e9+7; int vis[100010]; int main() { int n; cin>>n; ll sum = 1; int ans = 0; for(int i=1;i<n;i++) { if(__gcd(i,n) == 1) { vis[i] = 1; sum = sum*i%n; ans++; } } if(sum!=1) { ans--; vis[sum] = 0; } cout<<ans<<endl; for(int i=1;i<n;i++) { if(vis[i]) cout<<i<<" "; } }