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