[CodeForces948B]Primal Sport（数论）

2024-08-28 22:25:28

Description

Solution

设f(x)为x的最大质因子

那么由题意易得\(X_1\)的范围在\([X_2-f(X_2)+1,X2]\)

同理\(X_0\)的范围在\([X_1-f(X_1)+1,X1]\)

枚举\(X_1\)即可

Code

#include<cstdio>

#include<algorithm>

using namespace std;

int n,tmp,Ans=1e9,f[1000010];

void Init(){

	for(int i=2;i<=n;++i){

		if(!f[i]) for(int j=2;i*j<=1000000;++j)

			f[i*j]=i;

		f[i]=i-f[i]+1;

	}

}

int main(){

	scanf("%d",&n);

	Init();

	for(int i=f[n];i<=n;++i) Ans=min(Ans,f[i]);

	printf("%d\n",Ans);

	return 0;

}

最新文章

热门文章