1453 : 货币系统
时间限制Time Limit
1
秒Sec
内存限制Memory Limit
256
兆MB
提交次数Submitted
0
次Times
通过次数Solved
0
次Times
标准评测Standard Judge
题目描述Description
给定一个长度为 n 的升序数组 A，第 i 项的值为 A_i，其中 A_1=1。
用这个数组构建一个货币系统，对于任意正整数 x，定义换钱张数函数为 f(x,n)，其中 n 为数组长度。这个函数表示使用这一套货币系统支付 x 元时，如果要满足尽量先拿大面额纸币再拿小面额纸币的原则，需要拿出多少张纸币。对于任意正整数 x 和一个正整数 y\in [1,n]，f(x,y) 满足：
f(x,y)= \begin{cases} \lfloor\frac{x}{A_y}\rfloor+f(x\bmod A_y, y-1) & y > 1\\ x & y = 1 \end{cases}
你需要处理 q 组询问，每一组询问会给出一个整数 m，请回答有多少个正整数 x 满足 f(x,n)=m。
输入格式Input
输入第一行有两个正整数 n 和 q（1\le n\le 10^5,1\le q\le 10^6），表示数组 A 的长度和询问次数。
第二行有 n 个正整数 A_1,A_2,\ldots,A_n（1=A_1<A_2<\ldots<A_n\le 10^6），表示数组 A。
第三行有 q 个整数 m_1,m_2,\ldots,m_q（1\le m_i\le 10^9），其中 m_i 表示第 i 次询问的整数。
输出格式Output
输出一行 q 个用空格隔开的整数，第 i 个整数表示第 i 次询问的答案。
样例Sample
提示Hint
对于样例，给出的货币系统中纸币面额有 1 元、5 元、10 元、20 元、50 元和 100 元六种。按照规则，当你要支付 6 元时只能拿出两张纸币，即一张 1 元和一张 5 元，也就是 f(6,6)=2。虽然支付 6 元也可以使用六张 1 元，但是这种方案并不满足尽量拿大面额纸币的原则，也不满足本题函数的定义。