Fork me on GitHub

[构造][数论]CF1514C

怎么学构造啊呜呜呜

题目链接

首先有个很显然的性质:$kn+1$必定与$n$互质.所以我们一定不会选择与$n$不互质的数(因为这样的话最终乘出来的数一定会与$n$不互质,那么肯定余数不为$1$).
然后我们选出所有的与$n$互质的数之后,将这些数膜$n$意义下的乘积记为$p$,那么$p$也一定与$n$互质并且比$n$小,那么$p$这个数也一定在我们之前选择的那些与$n$互质的数中,所以这时候我们只需要判断$p$是否为$1$,如果为$1$,那么我们直接输出所有的与$n$互质的数即可,如果不为$1$,因为$p$一定是一个因子,我们把$p$删掉即可.

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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n , ans;
bool use[N];

int main ( void ) {
scanf ( "%d" , &n );
ans = n - 1;
memset ( use , true , sizeof ( use ) );
for ( int i = 1 ; i < n ; i++ ) {
if ( __gcd ( i , n ) != 1 ) {
use[i] = 0;
ans--;
}
}
int p = 1;
for ( int i = 1 ; i < n ; i++ )
if ( use[i] )
p = ( 1ll * p * i ) % n;
if ( p != 1 ) {
use[p] = 0;
ans--;
}
printf ( "%d\n" , ans );
for ( int i = 1 ; i < n ; i++ )
if ( use[i] )
printf ( "%d " , i );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:[构造][数论]CF1514C

文章作者:兮水XiShui丶

发布时间:2021年04月22日 - 12:04

最后更新:2021年04月22日 - 12:04

原始链接:http://krrrr.top/2021/04/22/构造-数论-CF1514C/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。