【问题描述】
给出n,求n!最右边非零的数。
【输入】
第一行一个整数T,表示数据组数
接下来每行一个整数n
【输出】
共输出T行,每行表示对应的答案
【样例输入】
1
5
【样例输出】
2
数据规模
30%, n≤30,T≤10
100%, n≤102009,T≤30
=================================================================================
10^2009次,很明显不能直接暴力了。如果直接暴力直接30分,像咱这样弱的话没考虑边界情况考试时就是20分。
其实考试中已经想完了解决算法了,只是觉得高精度取模很难写。但是突然经CB一讲,取的模都是4...
对于4取的模我们可以直接考虑这个数的最后两位就可以了....之后的2007位可以完全无视....
因为 N=P*100+C N MOD 4=(P*100+C)MOD 4= (P*100)MOD 4+C MOD 4=0+C MOD 4=C MOD 4.
沙茶一个只能面壁。
首先就是阶乘,对于末尾做贡献的数只有每一个数的个位,十位以上都可以无视(除了个位是0之外),接下来要排除掉0,0的个数取决于5的个数,因为很显然2的个数比5的个数多,5和2一结合就可以产生一个零,所以说我们可以通过求5的个数判断0的个数。
接下来就是判断末尾了。我们直接把每个数的个位相乘来算答案显然不理想,但是我们可以发现,这里的数字都是循环的!即从1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0...这样的循环下去,其中0对于末尾没有贡献,1贡献了末尾一个因子1, 2的贡献取决于它的个数,而它有一部分是与5结合产生0了,所以这一部分我们可以通过求出5的个数减去就可以了。而3的贡献也取决于个数,4也一样,5的贡献只有可能是5,6则只可能是6,7,8,9,的话同3.对于一个N设末尾的那一位为 P,则这个阶乘中 1~P的个数为 N div 10+1,P之后的个数为 N div 10,这里为什么不解释,就是按循环节算的。而DIV 10在高精度里面就是向左移动一位!方便的不得了!然后就是计算末尾贡献了。比如对于7, 1个7为7,2个7末尾为9,3个7末尾为3,4个7末尾为1,则7的乘方的末尾的数是按 7,9,3,1循环的,也就是说,我们用 N DIV 10 mod 4,取到的余数就是7正循环到哪儿,也就是7的贡献。这样子其实我们只需要原来那个高精度数的倒数第二位和第三位就可以了!这个题目跟高精度没有关系!
对于这个最后直接开个数组先存好每个数的贡献值,然后再最后相乘累加就可以了。
评论