C. Product 1 Modulo N
time limit per test
1 second
memory limit per test
256 megabytes
题目描述
Now you get Baby Ehab’s first words: “Given an integer n, find the longest subsequence of [1,2,…,n−1] whose product is 1 modulo n.” Please solve the problem. A sequence b is a subsequence of an array a if b can be obtained from a by deleting some (possibly all) elements. The product of an empty subsequence is equal to 1.
Input
The only line contains the integer n (2≤n≤10^5).
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
5
Output
3
1 2 3 Input
8
Output
4
1 3 5 7 Note
In the first example, the product of the elements is 6 which is congruent(同余) to 1 modulo 5. The only longer subsequence is [1,2,3,4]. Its product is 24 which is congruent to 4 modulo 5. Hence, the answer is [1,2,3].
题意
输入n。
有元素范围在[1,n-1]的序列满足，所有元素的累乘，模等于1。
求这样的序列所包含元素个数最多是多少个，元素分别是什么？
思路
product参数用来记录简化剩余系内元素的累乘。
1、__gcd(a,b)是c++自带的求最大公因数的函数，注意两个参数需均为long long型。
2、从1~n-1的数里，不与n互素的不会出现在所求数列里。原因：product%n = 1，则product与n互素。所以product的因子必须与n互素。所以所求序列是简化剩余系的子集。已知：简化剩余系的所有元素的累乘模n等于1或-1（简化剩余系内元素均有相应唯一逆元对应，只有1和-1没有），题目求序列元素最多时，所以：如果简化剩余系的所有元素的累乘模n等于1，则该系列就为简化剩余系；如果等于-1，则去掉n-1即可。
AC代码
#include<iostream>
#include<algorithm>
#include<math.h>
#include<vector>
typedef long long ll;
using namespace std;
const int N = 1e5+10;
ll n;
vector<int> v;
int main(){
cin>>n;
ll product = 1;
for(ll i=1;i<n;i++){
if(__gcd(i,n)==1){
v.push_back(i);
product*=i;
product = product%n;
}
}
if(product==1){
cout<<v.size()<<endl;
for(int i=0;i<v.size();i++){
cout<<v[i]<<' ';
}
}
else{
cout<<v.size()-1<<endl;
for(int i=0;i<v.size()-1;i++){
cout<<v[i]<<' ';
}
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103314.html
