输出某数与自身的平方数的后几位相同的数
时间: 2023-05-31 12:02:00 浏览: 30
解法一:
假设这个数为 $x$,则有:
$$x^2 \equiv x\pmod{10^k}$$
其中 $k$ 表示要求的后几位数的位数。我们可以从 $k=1$ 开始尝试,如果没有符合条件的数,则继续增加 $k$ 的值。
当 $k=1$ 时,上式等价于:
$$x^2 \equiv x\pmod{10}$$
即:
$$x(x-1) \equiv 0\pmod{10}$$
因此,$x$ 的末位只能是 $0$ 或 $1$。
当 $k=2$ 时,上式等价于:
$$x^2 \equiv x\pmod{100}$$
即:
$$x(x-1) \equiv 0\pmod{100}$$
因此,$x$ 的末两位只能是 $00$、$01$、$25$ 或 $76$。
当 $k=3$ 时,上式等价于:
$$x^2 \equiv x\pmod{1000}$$
即:
$$x(x-1) \equiv 0\pmod{1000}$$
因此,$x$ 的末三位只能是 $000$、$001$、$376$ 或 $625$。
当 $k=4$ 时,上式等价于:
$$x^2 \equiv x\pmod{10000}$$
即:
$$x(x-1) \equiv 0\pmod{10000}$$
因此,$x$ 的末四位只能是 $0000$、$0001$、$9376$ 或 $0625$。
以此类推,可以依次求出 $k=5,6,\cdots$ 时的可能末 $k$ 位数。
解法二:
观察到如果一个数与自身的平方数的后几位相同,那么这个数的末几位数必须与其平方数的末几位数相同。
因此,我们可以枚举末几位数,计算对应的平方数,然后判断这个数是否与其平方数的末几位数相同。具体来说,假设我们要求后 $k$ 位数相同的数,我们可以枚举末 $k$ 位数为 $x$,然后求出 $x$ 的平方数,再判断这个平方数的末 $k$ 位数是否等于 $x$。
这种方法的时间复杂度取决于枚举的位数和枚举的范围,通常比较适用于较小的 $k$ 值。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)