「FAOI-R1」完美的平方数 (C)
题目描述
给定一个正整数 $m$。现有 $Q$ 个询问,每个询问给定一个正整数 $n$,要求你从 $1,4,9,16,\ldots,m^2$ 中取出若干个数(**同一个数可以取出多次**),使它们的和**恰好**为 $n$。问最少取出多少个数?(如果无解,则输出 $-1$)
输入输出格式
输入格式
**本题有多组数据。**
第一行,一个正整数 $T$,代表数据组数。
对于每组数据:
第一行,两个正整数 $m,Q$。
下面 $Q$ 行,每行一个正整数 $n$。
输出格式
对于每组数据的每个询问,输出一行一个正整数,表示答案。
输入输出样例
输入样例 #1
5
1 5
1
2
3
4
5
5 5
8
20
25
37
49
11 1
179
13 1
507
19 1
841
输出样例 #1
1
2
3
4
5
2
2
1
4
4
3
3
4
说明
样例解释:
对于第一组数据,显然答案是 $n$,因为你只能取 $1$。
对于第二组数据:
- $8=2^2+2^2$;
- $20=4^2+2^2$;
- $25=5^2$;
- $37=5^2+2^2+2^2+2^2$;(或 $37=4^2+4^2+2^2+1^2$)
- $49=5^2+4^2+2^2+2^2$;(或 $49=4^2+4^2+4^2+1^2$)
- **请注意,$37=6^2+1^2$ 和 $49=7^2$ 都不是合法的方案,因为该数据中 $m=5$。**
------------
**本题采用捆绑测试。**
| Subtask 编号 | $m\le$ | $n \le$ | 分值 |
| :--: | :--: | :--: | :--: |
| $0$ | $30$ | $10^4$ | $40$ |
| $1$ | $30$ | $10^{18}$ | $30$ |
| $2$ | $500$ | $10^{18}$ | $30$ |
对于 $100\%$ 的数据,$1 \le T \le 30$,$1 \le Q \le 10^4$,$1 \le m \le 500$,$1 \le n \le 10^{18}$,单个测试点中所有数据的 $m$ 的和($\sum m$)满足 $1 \le \sum m \le 500$。