CF1514 C. Product 1 Modulo N [妙妙题]

传送门:CF

[前题提要]:感觉这道题是真的妙,解这道题的所有步骤都是一步一步按图索骥来的,有种玩解密游戏的感觉

---

题目很简单,就是求1~n中最长的子序列,使得这n个数的乘积模n为1.

乍一看很不好解决.那不妨先假设我们挑选了$k$个数,然后这$k$个数的乘积为$K$,$K$模$n$为1.也就是说$K=xn+1$,考虑解这个不定方程,根据裴属定理,我们会发现$gcd(K,n)|1$,也就是说我们选的数的乘积必须得与$n$互质.这就意味着我们选的每一个数都得与$n$互质.

很好,现在我们可以将序列中所有与$n$不互质的数去掉了,剩下的都是与$n$互质的数.我们想要留下来的数最多,所以我们考虑删掉最少的数,然后满足我们的题意.此时如果我们剩下来的数的乘积模$n$就为1的话,此时我们的答案显然就是这个序列中的数.如果不是的话,我们假设此时的乘积$K$,满足一下条件,$K=xn+b$,显然,因为我们的$K$与$n$互质,所以我们的$b$也必然与我们的$n$互质,我们现在需要的是余数为$1$,也就是把$b$变为1,因为$b$与$n$互质,所以$b$必然在我们选的序列中,所以此时我们只要把$b$这个数从我们的序列中删掉即可.此时我们的序列模$n$的余数就必然为$1$

最后感慨一下:这道题是真的妙.

---

#include 
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
inline void print(__int128 x){
	if(x<0) {putchar('-');x=-x;}
	if(x>9) print(x/10);
	putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
signed main() {
	int n=read();
	vector<int>v;
	int num=1;
	for(int i=1;i<=n;i++) {
		if(gcd(i,n)==1) {
			v.push_back(i);
			num=num*i%n;
		}
	}
	if(num==1) {
		cout<<v.size()<<endl;
		for(auto i:v) cout<<i<<" ";
		cout<<endl;
	}
	else {
		cout<<v.size()-1<<endl;
		for(auto i:v) {
			if(i==num) continue;
			cout<<i<<" ";
		}
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49