题解:
对于操作2来说, a – a % x[i] 就会到左边离a最近的x[i]的倍数。
也就是说 [ k * x[i] + 1, (k+1)* x[i] -1 ]这段区间的的数都会走到 k * x[i]上。
所以对于每个位置都先计算出他到右边最远的覆盖位置。
然后在反着求出每个位置能往左走走到的最远的位置。
代码:
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("___.txt","r",stdin);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e6 + ;
const int M = 3e7;
vector<int> in[N], out[N];
int x[N], to[N], rto[N];
int n;
int main(){
scanf("%d", &n);
for(int i = ; i <= n; ++i) scanf("%d", &x[i]);
int f = ;
int a, b;
scanf("%d%d", &a, &b);
sort(x+, x++n);
n = unique(x+, x++n) - (x+);
for(int i = ; i <= a-b; ++i) rto[i] = i + ;
for(int i = ; i <= n; ++i){
LL start = b / x[i] * x[i];
if(start < b) start += x[i];
while(start < a){
LL r = start + x[i] - ;
if(r > a) r = a;
rto[start-b] = max(rto[start-b], (int)(r-b));
start = r + ;
}
}
// cout << "ok1" << endl;
for(int l = , r = ; l <= a-b; ++l){
int nr = rto[l];
while(r <= nr){
to[r] = l;
++r;
}
}
int ans = , now = a-b;
while(now){
ans++;
now = to[now];
}
cout << ans << endl; return ;
}