51Nod 1124. N!的非0最低位(中国剩余定理)

日付: 10月 16, 2018

[N!的非零最低位问题 - 51Nod](https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1124)

## Problem
求$n!$的非零最低位。

数据范围：$2\le n\le 10^{1000}$

## Solution
首先记录一下错误解法：
1. 一开始想的是不计算10的倍数，然后所有数对10取模后相乘，这样就相当于$1 \sim 9$出现了$n/10$轮，剩下的数是$1 \sim n \% 10$。但是这样明显是错误的，因为像20这样的数会在答案里乘上一个2，不能忽略。
2. 考虑到这一点，相当于再递归一下，答案再乘上$n/10$的答案。但是在做乘法计算时，采用的方法是维护最小的非零位，这种做法是错误的，比如25乘4最小非零位是1，而按照上述做法应该是5乘4，算出来是2。
3. 看到讨论区大佬的评论“先把2，5去掉，分别对2，5，取余，中国剩余定理合并”。想到先算出5出现的次数，也就是$q = n/5$，那么$res = n! / (2^q 5^q)$就是去掉末尾0的结果。考虑到在5出现之前2已经出现了2和4，所以2出现的次数一定是大于q的，这说明结果对2取模一定为0，只需要计算对5取模的结果。计算时，一开始用了错解1中提到的方法，即找循环节，但又忘了计算模5为零的情况。

到错解3已经很接近正解了，结合错解2中的递归式，我们可以算出n!除去5的倍数对5取模的结果，然后再乘上$2^q$的逆元即可得到$res$。最后用中国剩余定理算出模10的值。

还需要注意以下几点：
1. 因为n非常大，需要高精度，用python写起来会轻松很多
2. 在算$2^q$时，因为q很大，使用欧拉降幂公式 $a^k\% m = a^{k\%phi(m)+phi(m)}, \quad k \ge phi(m)$ 可以加速计算
3. python的递归深度有限制，大概只有1000左右，需要调大最大递归深度

## Code
```python
import sys
sys.setrecursionlimit(10000)

def inv(x, p): return inv(p % x, p) * (p - p // x) % p if x > 1 else x

def crt(A, M):
    m, ans = 1, 0
    for x in M:
        m = m * x
    for i in range(len(A)):
        ans = (ans + A[i] * m // M[i] * inv(m // M[i] % M[i], M[i])) % m
    return ans

def calc(n):
    q = n // 5
    r = n % 5
    t = 4 if (q & 1) else 1
    for i in range(1, r + 1):
        t = (t * i) % 5
    k = q % 4 + 4 if q >= 4 else q
    t = t * inv((1 << k) % 5, 5) % 5
    if q > 0:
        t = t * calc(q) % 5
    return t

n = int(input())
print(crt([0, calc(n)], [2, 5]))

```

KONGROOの基地

このブログを検索

51Nod 1124. N!的非0最低位(中国剩余定理)

コメント

コメントを投稿