CF 1514C Product 1 Modulo N

题目描述

http://codeforces.com/contest/1514/problem/C

Solution

首先与 $n$ 不互质的数肯定不能选

那么是否我们选择所有与 $n$ 互质的数最终乘积一定是 $1$ 呢？

答案显然是否定的，但是这给我们提供了另一个思路

这些与 $n$ 互质的数的乘积一定与 $n$ 互质，且在模 $n$ 后也一定与 $n$ 互质，原因就是 $(a,b)=(a,b\bmod a)$

那么模 $n$ 后得到的这个数与 $n$ 互质且小于 $n$，说明这个数已经被我们选了，那么我们剔除这个数即可，并且这样长度一定是最长的

#include <iostream>
#include <cmath>
#include <vector>
#define maxn 100010
#define ll long long
using namespace std;

int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }

int n;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    ll mul = 1; vector<int> ans;
    for (int i = 1; i < n; ++i) 
        if (gcd(i, n) == 1) mul = mul * i % n;
    if (mul == 1) {
        for (int i = 1; i < n; ++i)
            if (gcd(i, n) == 1) ans.push_back(i);
        cout << ans.size() << "\n";
        for (auto u : ans) cout << u << " "; 
    } else {
        for (int i = 1; i < n - 1; ++i)
            if (gcd(i, n) == 1) ans.push_back(i);
        cout << ans.size() << "\n";
        for (auto u : ans) cout << u << " "; 
    }
    return 0;
}