BZOJ 3552: 最右非零的数

给出正整数 N（可能有前导 0），请求出 N!最右非零的数位的值。

Input

第一行一个数 T 表示数据组数 下接 T 行每行一个数 N 表示一组数据

Output

对于每组数据，输出一行一个数表示这组数据的答案

Sample Input

2
5
4

Sample Output

2
4

Solution

随便 lucas 一下就好了，然而懒得写高精，就用了 python，于是实力 rank last。

Code

T=int(raw_input())
for I in range(T):
    n=int(raw_input());t=n;a=0;b=0;c=1
    while t>0:t/=2;a+=t
    while n>0:c=c*[1,1,2,1,4,4,4,3,4,1][n%10]%5;n/=5;b+=n
    a=a-b+1
    if a>1:a=0
    t=3
    while b>0:
        if b&1:c=c*t%5
        t=t*t%5
        b/=2
    print (a*5+c*6)%10

日期： 2016-12-16

标签： BZOJ lucas定理

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/154/ 查看。