设 $d=\gcd(a_1, a_2, \dots, a_f)$，则题目要求的是 $d$ 为 $1$ 时 $\sum_{i=1}^fa_i=n$ 的答案。而对于 $\sum_{i=1}^fa_i=n$ 这个问题的答案记为 $g(f, n)$。则用插板法可以容易地求出 $g(f, n)=(^{n-1}_{f-1})$，则接下来的问题就是消去 $d\not=1$ 时的答案。首先显然有 $d|n$，且这个问题应当是使用容斥解决，而对于有关 $\gcd=1$ 的容斥，可以使用莫比乌斯反演。莫比乌斯反演的结论是若有 $f(n)=\sum_{d|n}g(d)$，则 $g(n)=\sum_{d|n}f(d)\times\mu(\frac nd)$ 。此题中，设整道题的答案为 $h(f, n)$，则有 $g(f, n)=\sum_{d|n}h(f, \frac nd)$，其中 $h(f, \frac nd)$ 的意义为长度为 $f$ 的数列 $\gcd=d$ 时的答案。此时使用莫比乌斯反演，就有 $h(f, n)=\sum_{d|n}g(f, d)\times\mu(\frac nd)$。

使用线性筛筛出 $\mu$，每个询问直接 $O(\sqrt n)$ 卷积即可。时间复杂度 $O(q\sqrt n)$。

Code 在此。