Number Transformation II

题意翻译

#### 题目描述 给定 $n$ 个正整数 $x_i$ 和两个非负整数 $a$ 、 $b$ ，（ $b\leq a$ ），你每次可以进行以下两操作中任一个： 1. $a=a-1$ 2. $a=a-a\ mod\ x_i(1\leq i\leq n)$ 问要使 $a$ 变成 $b$ 至少需要多少次操作 #### 输入格式 第一行一个整数 $n$ 。 第二行 $n$ 个整数 $x_i$ 。 第三行两个整数 $a$ 、 $b$ 。 #### 输出格式 一个整数，表示将 $a$ 变成 $b$ 的最少操作数。 #### 数据范围 $1\leq n\leq 10^5,2\leq x_i\leq 10^9$ $0\leq b\leq a\leq 10^9,a-b\leq 10^6$

题目描述

You are given a sequence of positive integers $ x_{1},x_{2},...,x_{n} $ and two non-negative integers $ a $ and $ b $ . Your task is to transform $ a $ into $ b $ . To do that, you can perform the following moves: - subtract 1 from the current $ a $ ; - subtract $ a $ mod $ x_{i} $ $ (1<=i<=n) $ from the current $ a $ . Operation $ a $ mod $ x_{i} $ means taking the remainder after division of number $ a $ by number $ x_{i} $ . Now you want to know the minimum number of moves needed to transform $ a $ into $ b $ .

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1<=n<=10^{5} $ ). The second line contains $ n $ space-separated integers $ x_{1},x_{2},...,x_{n} $ ( $ 2<=x_{i}<=10^{9} $ ). The third line contains two integers $ a $ and $ b $ ( $ 0<=b<=a<=10^{9} $ , $ a-b<=10^{6} $ ).

输出格式

Print a single integer — the required minimum number of moves needed to transform number $ a $ into number $ b $ .

输入输出样例

输入样例 #1

3
3 4 5
30 17

输出样例 #1

6

输入样例 #2

3
5 6 7
1000 200

输出样例 #2

206