C.Product1ModuloN

C. Product 1 Modulo N

题目链接

题目大意
给你一个数要求让你从1到n-1中尽可能多的取数使得乘积模n等于1

思路
你只能那和n互质的数&＃xff0c;否则在模n时&＃xff0c;其取模结果不会为1&＃xff0c;gcd&＃xff08;p%n&＃xff0c;n)&＃61;gcd(p,n),也就是如果n和k*n&＃43;1互质的话&＃xff0c;那么&＃xff0c;存在一个数都能被这两个数整除&＃xff0c;那么这个数一定是1&＃xff0c;所以你只需要取与n互质的数放到序列中&＃xff0c;但是有可能这个乘积模n不是1&＃xff0c;那么你将这个不是1的余数在原序列中删除&＃xff0c;就可以的到答案&＃xff0c;为什么呢&＃xff0c;你除去的这个余数相当于相当于整除余数本身&＃xff0c;由于整除本身是1&＃xff0c;所以得到取模后的结果一定为1

通过代码

#include
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define sl(n) scanf("%lld",&n)
#define pl(n) printf("%lld",n)
#define sdf(n) scanf("%lf",&n)
#define pdf(n) printf("%.lf",n)
#define pE printf("\n")
#define ull unsigned long long
#define pb push_back
#define debug(a) cout<
#define me(a) memset(a,0,sizeof(a))
#define pre(n) for(ll i&＃61;1;i<&＃61;n;i&＃43;&＃43;)
#define rep(n) for(ll i&＃61;n;i>&＃61;1;i--)
#define ph push
#define pi pair
#define fi first
#define se second
const ll mod &＃61; 1e9&＃43;7;
using namespace std;
ll a[100010];
int main(){ll n,q&＃61;1;sl(n);for(ll i&＃61;1;i<n;i&＃43;&＃43;){if(__gcd(i,n)&＃61;&＃61;1){a[i]&＃61;1;q&＃61;i*q%n;}}if(q!&＃61;1)a[q]&＃61;0;cout<<count(a&＃43;1,a&＃43;n,1);pE;for(ll i&＃61;1;i<n;i&＃43;&＃43;)if(a[i]&＃61;&＃61;1)cout<<i<<&＃39; &＃39;;return 0;}