CF923A题解

CF923A

1.题目描述

Alice 和 Bob 以一个小游戏作为一天的开始。他们首先选一个整数 $x_0; (x_0\ge 3)$。

Alice 先手，然后他们轮流操作。在第 $i$ 轮（$i\ge 1$）中，轮到的玩家选一个小于 $x_{i-1}$ 的质数 $p_i$，然后找到一个最小的整数 $x_{i}$ 满足 $x_{i}\ge x_{i-1}$ 且 $x_{i}$ 为 $p_i$ 的倍数。

他们玩了两轮之后忘记了初始时 $x_0$ 的值。现在给你 $x_2$，请你求出 $x_0$ 最小可能是多少。请注意，玩家并不一定采取最优策略。你需要考虑所有可能的游戏过程。

2.思考历程

首先，我想了一下直接通过 $x_2$ 算出 $x_0$ ，但是发现这是条死路

接下来，我想了一下，这道题可以不用反推，为啥我不枚举 $x_0$ 正着推一遍

但是我发现还是要迭代2次，第一次的选择会严重影响第二次的选择

都到这里了，我发现，我似乎可以枚举 $x_1$ ，这样一次选择不会影响后面的选择（因为没有后面了）

首先，判断通过选小于 $x_1$ 的质数的倍数能否使其等于 $x_2$

直接质因数分解 $x_2$ ，再看哪一些质因数小于 $x_1$ ，再看能否凑出 $x_2$ ，这里是 $O(log log n)$ 的，质因数分解可以提前做，判断质数用欧拉筛

接下来，通过 $x_1$ 倒推 $x_0$ ，这里十分简单。

我们发现假设 $x_1$ 有一个质因数 $k$ ，那我们可以通过 $k$ 来拼出最小的 $x_0$

这里最小的 $x_0$ 是除以 $k$ 的余数为 $1$ 的 $x_0$ ，也就是 $x_1-k+1$

所以要让 $x_0$ 尽可能的小，那我们就要选出最大的 $k$ ，也就是最大质因数

这里可以使用欧拉筛预处理

这很好想，不必赘述

于是所有取个min，就做完了

3.Code

#include<bits/stdc++.h>
using namespace std;
int x,prime[2000010],cnt,vis[2000010],l[2000010];
vector<int>v;
main(){
	cin>>x;
	vis[1]=1;
	for(int i=2;i<=x;i++){
		if(!vis[i])prime[++cnt]=i,l[i]=i;
		for(int j=1;j<=cnt;j++){
			if(i*prime[j]>x)break;
			vis[i*prime[j]]=1;
			l[i*prime[j]]=l[i];
			if(i%prime[j]==0)break;
		}
	}
	int ans=1e6;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			if(!vis[i])v.push_back(i);
			if(i*i!=x and !vis[x/i])v.push_back(x/i);
		}
	}
	for(int i=3;i<=x;i++){
		int flag=0;
		for(auto j:v){
			if(j<=i){
				if(i%j==0){
					if(i==x)flag=1;
				}else{
					if((i/j+1)*j==x)flag=1;
				}
			}
		}
		if(!flag)continue;
		//cout<<i<<" "<<l[i]<<endl;
		ans=min(ans,i-(l[i]==i?1:l[i])+1);

	}cout<<ans;
	return 0;
}