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 个 九位数 满足条件。

#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");
    }
}