题目的关键："每次选取一个选取后发给用户的总金额不超过 $c$ 最大面额"。这就表明了，一个数的拆分是完全确定的，其中并不涉及任何优劣决策。对于 $a$ 如此之大的数据范围，我们肯定是要将 $a_i$ 做为分割点的，而不是一个一个来。那么设计状态 $x_i$ 表示小于 $a_i$ 的数中，需要纸币个数最多的那个数；$y_i$ 表示最多是多少。

考虑 $i$ 到 $i+1$ 的转移：显然为了使得所用纸币个数更大，$x_{i+1} \in [a_i,a_{i+1})$。由题意，这一范围内纸币一定是取 $a_i$。那么尽量多取就行了，可取个数 $tmp$ 为 $\lfloor \frac{a_{i+1}-x_{i}-1}{a_i} \rfloor$，递推有 $x_{i+1} \gets x_i + tmp \times a_i,y_{i+1} \gets y_i + tmp$。

我们现在考虑怎么应对询问。我们在上面预处理的过程中只是挖掉了 $a_i$ 这个点，在回答询问时，先找到第一个小于 $b$ 的点，然后令 $tmp = \lfloor \frac{a_{i+1}-x_{i}}{a_i} \rfloor$，类似得出结果即可。

时间复杂度：$O(n+q \log n)$。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n,q,a[N],x[N],y[N];

template <typename T>
inline void read(T &x){
	x = 0;
	static char c;
	static bool f;
	c = getchar(), f = 0;
	while(c<'0'||c>'9'){ if(c == '-')f = 1; c = getchar(); }
	while('0'<=c&&c<='9')x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	x = f ? -x : x;
}

signed main(){
	read(n);
	for(int i = 1;i<=n;++i)read(a[i]);
	for(int i = 1;i<n;++i){
		int tmp = (a[i+1] - x[i] - 1) / a[i];
		x[i+1] = x[i] + tmp * a[i], y[i+1] = y[i] + tmp;
	}
	read(q);
	int val; while(q--){
		read(val);
		int cur = upper_bound(a+1,a+n+1,val)-a-1;
		int it = (val - x[cur]) / a[cur];
		printf("%lld %lld\n",x[cur] + it * a[cur], it + y[cur]);
	}
	return 0;
}