AT_joisc2007_factor 階乗 (Factorial) 题解

TimelessWelkin · 2025-10-07 15:55:45 · 题解

观察数据范围可以发现 2 \le n \le 10^9。若使用朴素的暴力，最坏时间复杂度可以到达 O(n) （即 n 为质数），说明朴素的暴力难以通过此题。

不难发现，若从 1 开始枚举 i，若 \gcd(i,n) !=1，则 n \rightarrow n \div \gcd(i,n)。若在操作前发现 n|i，则说明从 1 乘到 i 是 n 的倍数，答案即为 i。

这是题解区域里面前面大佬们的做法，但不难发现如果 n 是一个较为大的质数如 998244353 时间复杂度任较大。所以需要在每次修改后（以及开始之前）查询是否为质数，若为质数且比当前 i 大，则答案即为该质数。

代码如下：

#include<bits/stdc++.h>
using namespace std;
bool isprime(int x){
    for(int i=2;i*i<=x;i++)
        if(x%i==0)return false;
    return true;
} 
int main(){
    int n,m;
    scanf("%d",&n);m=n;
    if(isprime(n)){
        printf("%d\n",n);
        return 0;
    }
    for(int i=1;i<=m;i++){//从1开始枚举，至多到n（显然到不了） 
        if(i%n==0){
            printf("%d\n",i);
            return 0;
        }
        if(__gcd(n,i)!=1){
            n/=__gcd(n,i);
            if(isprime(n) && n>i){//如果是质数且质数>i则输出该质数
                printf("%d\n",n);
                return 0;
            }
        }
    }
}