{"problem":{"name":"「FAOI-R1」完美的平方数","description":{"content":"给定一个正整数 $m$。现有 $Q$ 个询问，每个询问给定一个正整数 $n$，要求你从 $1,4,9,16,\\ldots,m^2$ 中取出若干个数（**同一个数可以取出多次**），使它们的和**恰好**为 $n$。问最少取出多少个数？（如果无解，则输出 $-1$）","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8447"},"statements":[{"statement_type":"Markdown","content":"给定一个正整数 $m$。现有 $Q$ 个询问，每个询问给定一个正整数 $n$，要求你从 $1,4,9,16,\\ldots,m^2$ 中取出若干个数（**同一个数可以取出多次**），使它们的和**恰好**为 $n$。问最少取出多少个数？（如果无解，则输出 $-1$）\n\n## Input\n\n**本题有多组数据。**\n\n第一行，一个正整数 $T$，代表数据组数。\n\n对于每组数据：\n\n第一行，两个正整数 $m,Q$。\n\n下面 $Q$ 行，每行一个正整数 $n$。\n\n## Output\n\n对于每组数据的每个询问，输出一行一个正整数，表示答案。\n\n[samples]\n\n## Note\n\n**样例解释：**\n\n对于第一组数据，显然答案是 $n$，因为你只能取 $1$。\n\n对于第二组数据：\n\n- $8=2^2+2^2$；\n- $20=4^2+2^2$；\n- $25=5^2$；\n- $37=5^2+2^2+2^2+2^2$；（或 $37=4^2+4^2+2^2+1^2$）\n- $49=5^2+4^2+2^2+2^2$；（或 $49=4^2+4^2+4^2+1^2$）\n- **请注意，$37=6^2+1^2$ 和 $49=7^2$ 都不是合法的方案，因为该数据中 $m=5$。**\n\n------------\n\n| 测试点编号 | $m\\le$ | $n \\le$ | 分值 |\n| :--: | :--: | :--: | :--: |\n| $1$ | $30$ | $10^4$ | $40$ |\n| $2 \\sim 3$ | $30$ | $10^{18}$ | $15 \\times 2$ |\n| $4 \\sim 9$ | $500$ | $10^{18}$ | $5 \\times 6$ |\n\n对于 $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$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8447","tags":["动态规划 DP","数论","O2优化","背包 DP"],"sample_group":[["5\n1 5\n1\n2\n3\n4\n5\n5 5\n8\n20\n25\n37\n49\n11 1\n179\n13 1\n507\n19 1\n841","1\n2\n3\n4\n5\n2\n2\n1\n4\n4\n3\n3\n4"]],"created_at":"2026-03-03 11:09:25"}}