https://scg3.piaoztsdy.cn/p/107
首先特判 的情况。
很明显，当 时，，因此答案不可能大于 。
当 为质数时，由威尔逊定理可得：
因此答案一定是 。
当 为合数时，由题意可知 ，其中 是 的最小素因子。
显然 ，并且答案不大于 ，暴力枚举即可。
最终的时间复杂度是 。
#include <bits/stdc++.h>
using namespace std;
bool prime(int n)
{
if (n == 1) return false;
for (int i = 2; i * i <= n; i++)
if (n % i == 0) return false;
return true;
}
int solve(int n)
{
if (n <= 2) return n - 1;
if (prime(n)) return n - 2;
long long f = 1;
int ans = 1;
for (int i = 2; n % i != 0; i++)
{
f = f * i % n;
if (f == 1) ans = i;
}
return ans;
}
int main()
{
freopen("factorial.in", "r", stdin);
freopen("factorial.out", "w", stdout);
int T;
cin >> T;
while (T--)
{
int n;
cin >> n;
cout << solve(n) << endl;
}
return 0;
}
暂无评论