3777: 学习除法(第五轮03)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
牛牛上二年级了，今天学习了除法，他想要通过若干次除法将一个数字 x 变得不超过 y。
现在牛牛有很多个除数可以选择，给定一个长度为 τ 的序列 b。表示除数 i 的花费是 bi，
牛牛可以用这个除数把 x 变为 x/i。每种除数可以使用无限次。
多组询问， 每组询问输入两个数 x, y， 表示牛牛需要使用若干次除法把 x 变得不超过 y， 对于每一组询问你都要输出一个答案表示求最小花费，保证题目一定有解。
大样例：sample.zip
输入
输入包含 q + 2 行。
第一行输入两个正整数 τ, q。
第二行输入 τ 个正整数， 第 i 个数表示 bi 。
接下来 q 行，每行两个正整数 x, y，如题意所示。
输出
输出 q 行。
每行输出一个数，表示对应询问的答案。
样例输入 复制
5 3
4 3 2 2 4
4 3
1 4
5 1样例输出 复制
2
0
2提示
【样例 1 输入】
5 3
4 3 2 2 4
4 3
1 4
5 1
【样例 1 输出】
2
0
2
【样例 2 输入】
5 3
1 4 3 5 2
2 1
4 5
1 4
【样例 2 输出】
2
0
0
【备注】
- 对于所有的测试点， 1 ≤ bi ≤ 10^9 。
- 对于测试点1 ∼ 2： 1 ≤ τ, q, x, y ≤ 10^2 。
- 对于测试点3 ∼ 4： 1 ≤ τ, q, x, y ≤ 10^3 。
- 对于测试点5 ∼ 10： 1 ≤ τ, q, x, y ≤ 10^5 。