AT_joisc2007_factor 階乗 (Factorial) 题解

观察数据范围可以发现

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

大，则答案即为该质数。

代码如下：

CPP

#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;
			}
		}
	}
}

AT_joisc2007_factor 階乗 (Factorial) 题解

文章操作

相关推荐

评论

AT_joisc2007_factor 階乗 (Factorial) 题解