这是本文档旧的修订版!
给定T个询问,每次询问一个$N$,要求输出所有$N$位的数$x$的满足$x*x$的后$N$位等于$x$.(不妨假设$x$为$i$位)。
$N \le 500$,$T \le 1000$。
首先我们不难想到满足条件的1位数分别为0,1,5,6。我们可以想到,满足条件的两位数的个位必定是满足条件的一位数…N位后面的数字必定是N-1位满足条件的数字,由于有这样的性质,我们可以在这4个数的基础上在前面添数字进行验证,由于最多有500位,需要高精度,复杂度应为$(N*N*4*10)$,特别的,我们需要注意,满足条件的还前导0的N位数我们也要考虑,例:我们需要从0625推出90625,4位不保存则会少解。然后可以发现,这样到N位满足的不会超过4个,且必定有两个为000…1和000…0.然后发现用高精预处理答案会T(或许写万进制或者亿进制不会?),其实只要通过高精度的算法把500位的两个解弄出来每次去掉最高位就可以了(无前导0即为解,有则不为)。
第一小时:tyx在写H题,但是没有写出来;gyp和lxh想出了A题思路,lxh发现G题有很多人过于是A了G题。
第二小时:三个人一起在想D题,没有想出来。tyx和lxh想出了B题怎么写,lxh开始写B题。
第三小时:gypA了J题,lxhA了B题,tyx在想D题。
第四小时:gyp发现数据比较水,tyx由此想到了$O(n^2T)(n \le 1000,T \le 200)$的方法A了D题。lxhA题的高精度超时。
尽量不要三个人同时想一道题;在别的题没有明确解法的情况下,有想法的题一定要尝试一下;一定要先把所有题都看一遍。