1514 C
题意
给出一个数n，求[1,2,3...n-1]的某个最长子序列，这个子序列的元素乘积模n余1。
思路
这是个思维题，一个数学公式
\[x \equiv 1(mod n) \rightarrow kx\equiv k(mod kn) \]所以子序列中的元素与\(n\)互质，累乘结果模\(n\)后如果不是1，那么将序列中等于结果的元素去掉
代码
void solve()
{
cin>>n;
vector<int> a;
for(int i=1;i<=n;i++) if(__gcd(i,n)==1) a.push_back(i);
int ans=1;
for(auto x:a) ans=ans*x%n;
ans=ans%n;
if(ans==1)
{
cout<<a.size()<<endl;
for(auto x:a) cout<<x<<" ";
cout<<endl;
}
else
{
cout<<a.size()-1<<endl;
for(auto x:a) if(ans!=x) cout<<x<<" ";
cout<<endl;
}
}