算法
(数论、构造) $O(n\log n)$
记 $\varphi(n)$ 为 $n$ 之前与 $n$ 互素的正整数的个数
可以取出 $\{1, 2, \dots, n - 1\}$ 中所有与 $n$ 互素的数,然后把他们做乘积并对 $n$ 取模,最后的结果只有 $1$ 和 $n - 1$ 两种可能,若结果为 $1$,那么最长子列长度为 $\varphi(n)$,否则为 $\varphi(n) - 1$
结论:对于 $n = 1, 2, 4$,答案为 $1$。$n = p^k \ (k \geq 1)$ 或 $2p^k (k \geq 1)$,其中 $p$ 为奇素数,答案为 $\varphi(n) - 1$,其余情况答案为 $\varphi(n)$。求长度的复杂度和质因数分解的复杂度一样,而用 pollard-rho
可以做到 $O(n^{\frac{1}{4}})$。
当然如果不知道结论,对于大整数的情况,可以考虑类似于组合数取模的做法。
C++ 代码
#include <bits/stdc++.h>
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define pb push_back
using std::cin;
using std::cout;
using std::vector;
using vi = vector<int>;
using ll = long long;
int main() {
int n;
cin >> n;
if (n == 2) cout << "1\n1";
else {
vi v;
ll now = 1;
rrep(i, n) {
if (std::gcd(i, n) == 1) {
v.pb(i);
now = now * i % n;
}
}
if (now == n - 1) v.pop_back();
cout << v.size() << '\n';
for (int x : v) cout << x << " ";
}
return 0;
}