mcfx's blog - lucas定理
/category/luc/
-
BZOJ 3552: 最右非零的数
/archives/154/
2016-12-16T23:38:00+08:00
###Description
给出正整数N(可能有前导0),请求出N!最右非零的数位的值。
###Input
第一行一个数T表示数据组数
下接T行每行一个数N表示一组数据
###Output
对于每组数据,输出一行一个数表示这组数据的答案
###Sample Input
2
5
4
###Sample Output
2
4
###Solution
随便lucas一下就好了,然而懒得写高精,就用了python,于是实力rank last
###Code
```python
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
```