P15500 [ICPC 2025 APC] Squares on Grid Lines
题目描述
在一个二维平面上，有一个边长为 $n$ 的正方形，它被划分成 $1 \times 1$ 的单元格网格，总计有 $n^{2}$ 个单元格。
你的任务是回答 $q$ 个查询，查询编号为 $1$ 到 $q$，描述如下。在第 $i$ 个查询中，你会得到一个实数 $s_{i}$，你需要计算在平面上放置四个点的方案数，使得：
- 每个点都位于某个单元格的边界上（不必是同一个单元格），且
- 这四个点构成一个面积为 $s_{i}$ 的正方形的顶点。
这里，由这些点构成的正方形的边不必与单元格的边平行。如果存在无穷多种有效放置方式，你必须报告这一情况。
如果存在一个点出现在一种放置方式中但不出现在另一种中，则认为这两种放置方式不同。
输入格式
输入的第一行包含两个整数 $n$ 和 $q$（$1\le n\le 2000$，$1\le q\le 100\,000$）。接下来的 $q$ 行中的第 $i$ 行包含一个实数 $s_{i}$（$0.01\le s_{i}\le n^{2}$），小数点后恰好有两位数字。
输出格式
输出 $q$ 行。第 $i$ 行应包含第 $i$ 个查询的有效放置方式的数量。如果存在无穷多种，则输出 $-1$。
说明/提示
**样例输入/输出 #1 的解释**
对于查询 $1$ 和 $2$，有效的放置方式如图 I.1 所示。上方的两种放置方式对应查询 $1$，下方的四种放置方式对应查询 $2$。在每种放置方式中，阴影区域表示由这些点构成的正方形。
:::align{center}
图 I.1：样例输入 #1 的图示。
:::
翻译由 DeepSeek 完成