C. Product 1 Modulo N (Codeforces Round #716 (Div. 2))

問題

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

問題概要

整数nが与えられる。[1, 2, ..., n-1]の部分列で要素の積をnで割ったあまりが1となるもののうちで最長のものを求めよ。

考察

nと互いに素でない数は含めることができません。gcdが1でないため、nで割ってもあまりが1になりません。

nと互いに素であるものをすべて含めた場合、nで割ったあまりrが1であればそれが答えですし、rが1でなければあまりの数を除去したもの（nと互いに素であるものすべての積がp+rと表せて、rを除去するとは全ての積からrを割るつまり(p+r)/r = p/r + 1）が答えです。

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    vector<int> ans;
    ans.emplace_back(1);
    long long r = 1;
    for (long long i = 2; i < n; i++) {
        if (gcd(i, n) == 1) {
            ans.emplace_back(i);
            r *= i;
            r %= n;
        }
    }
    int m = (int)ans.size();
    cout << (r == 1 ? m : m - 1) << endl;
    for (int i = 0; i < m; i++) {
        if (ans[i] == 1 or ans[i] != r) cout << ans[i] << (i == m - 1 ? '\n' : ' ');
    }
}

反省

nが偶数のとき、偶数は含まれないということはすぐわかったのですが、偶数に限らずnと互いに素という条件にたどり着けず・・・。うーん。