题解 P2368 【EXCEEDED WARNING B】
heidoudou
2018-09-14 00:20:16
#### Description
求有多少个平方后末尾为 `987654321`的 $n$ 位数
#### Analysis
这种数肯定不多，问题是如何找到这种数？
有一个常识是： $(100a + b)^2$， 如果 $a$ 任意，$b < 100$， 那么平方数的末两位数字只会由 $b$ 确定。
这个结论可以推广到 $(10^ka + b)^2$ 上。
最终只要找 $(10^{10}a + b)^2 \mod 10^{10} = 987654321$ 的 $b$ 就可以了。
因此就可以这样找：
1. 先找 $b$ 的个位，肯定只有 $1, 9$ 满足平方数末尾是 $1$
2. 再找 $b$ 的十位，用 `0 ~ 9` 十个数字拼上前面找的个位数，看看能不能得到 $21$
3. 再找 $b$ 的百位，用 `0 ~ 9` 十个数字拼上前面找的两位数，看看平方能不能得到 $321$
4. ...
最后在到第九位的时候，会发现，只有 8 个 **九位数** 满足条件。
```cpp
#include <cstdio>
#include <vector>
using namespace std;
typedef long long INT64;
const INT64 tail = 987654321;
int main()
{
vector<int> nums[10];
nums[0].push_back(0);
vector<int>::iterator it;
int n;
for (int i = 1, base = 10; i < 10; ++i, base *= 10)
{
for (int d = 0; d < 10; ++d)
for (it = nums[i - 1].begin(); it != nums[i - 1].end(); ++it)
{
n = base / 10 * d + *it;
if ((INT64)n * n % base == tail % base)
{
printf("%d %lld\n", n, (INT64)n * n);
nums[i].push_back(n);
}
}
printf("\n");
}
}
```