2018年北京小学生信息学科普日试题题解（下）

4

进制转换

问题描述

问题分析

（1）将n进制数字转化成10进制数字。

方法：按位乘n的i次方后相加。

（2）将10进制数字转化成m进制数字。

方法：反复除m取余数，除m的得数再取余数，直到得数为0，把余数按顺序从低位到高位写出即可。

AC代码

5

同余问题

问题描述

问题分析

对于n位的十进制整数D，设它的数位从低位到高位分别为d₀,d₁…d_n-1，则有： 

此时，利用乘法分配律，将D²拆分成多项式每一项分别相乘：

 

对于任意整数D，将后5位数留下，可以将其写成D=a*10⁵+b的形式，其中b=Dmod10⁵，即D的后5位。

那么有D²=（a*10⁵+b）²=a²*10¹⁰+b²。此时a²*10¹⁰mod10⁵=0，因此：D²的后5位仅与D后5位的平方有关。因此要想求D²的后5位，只需求出（Dmod10⁶）²即可。

于是当n≤5，以直接暴力求解.

否则，先暴力求出0到99999中所有平方后5位为54321的数的数量C，这样以10⁵为周期，只要把所有n位数的数量除以10⁵，再乘以C，就是所有n位数中平方后5位为54321的数量。

AC代码

转自公众号：
信息学少儿编程