原式可以表达为n!/(n-m)!
把10分解为2*5
f(n)代表n!里不含2和5因子的结果。
f(n)%2=a
f(n)%5=b
最后求一个x同时满足
s=a (mod 2)
s=b (mod 5)
然后n!=2^x*5^y
s*2(x-y)%10就是答案了。
求解f(n)%2可以按下面的方法求：
下面要用到一个函数，c(a,p)
表示，a!里有多少个素数p因子。
求n!/2^c(n,2)%2应该好求的用递归
然后1/((n-m)!/2^c(n-m,2))%2可以用逆元来转化的。
gcd(a,p)==1
那么1/a= a^(p-2) (mod p)
最后里面还有5的因子也可以用逆元来除掉。
这样就可以求出f(n)%2
f(n)%5也可以用同样的方法来求。
复杂度低，0MS AC

7141833 yygy 1150 Accepted 148K 0MS C++ 2154B 2010-07-12 21:04:52 

• Re:用中国剩余定理可解此题 (4) oracle_ 2014-01-22 20:11:13
  • 里面不是解释了吗 (8) yygy 2014-01-23 10:07:27