C. Number Transformation II
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given a sequence of positive integers x1, x2, ..., xn 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 xi (1 ≤ i ≤ n) from the current a.
Operation a mod xi means taking the remainder after division of number a by number xi.
Now you want to know the minimum number of moves needed to transform a into b.
Input
The first line contains a single integer n (1 ≤ n ≤ 105). The second line contains n space-separated integers x1, x2, ..., xn(2 ≤ xi ≤ 109). The third line contains two integers a and b (0 ≤ b ≤ a ≤ 109, a - b ≤ 106).
Output
Print a single integer — the required minimum number of moves needed to transform number a into number b.
Examples
input
3
3 4 5
30 17
output
6
input
3
5 6 7
1000 200
output
206
/*
CodeForces346 C. Number Transformation II 给你两个数a,b
1.每次对于当前的a减去1
2.每次对于当前的a减去 a%(ta[i]) 求最少多少次能得到b
类似于贪心,每次减去尽可能多的值。但是一直TLE- -. 后来可以发现a~a-a%ta[i]的所有值
如果减去a%ta[i],都会等于同一个值。 如果当a-a%ta[i] < b时,ta[i]可以说在后面的
搜索就没有作用了.于是乎把ta[i]除去. hhh-2016-04-16 17:15:20
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <math.h>
using namespace std;
#define lson (i<<1)
#define rson ((i<<1)|1)
typedef long long ll;
const int mod = 1000000009;
const int maxn = 100040;
int ta[maxn];
int main()
{
int n;
while( scanf("%d",&n) != EOF)
{
int num = 0;
int a,b;
for(int i =0; i < n; i++)
{
scanf("%d",&ta[i]);
}
sort(ta,ta+n);
n = unique(ta,ta+n)-ta;
scanf("%d%d",&a,&b);
while(a > b)
{
int cur = a - 1;
for(int i =n-1; i >= 0; i--)
{
if(a-a%ta[i] >= b)
cur = min(a-a%ta[i],cur);
}
a = cur;
num ++;
if(a == b) break;
while(n)
{
if(a-a%ta[n-1] < b)
n--;
else
break;
}
}
printf("%d\n",num);
}
return 0;
}