301832: CF346C. Number Transformation II
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
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