回 帖 发 新 帖 刷新版面

主题:快给答案!

我们这里的考试题中有一道这样的题:
输入一个数N(10000<N<10^10),求出N!最后一位非0的数字。
(别看这道题只要会高精度就行,因为N过大,要算很长很长时间,现要求2分钟内出结果)

回复列表 (共3个回复)

沙发

弱弱的问下 n!是n 的阶乘
阶乘怎么算?
是不是  n*(n-1)*(n-2)........*2?
那恭喜了...10^6无论算法怎么样都会超过2min

板凳

哈哈!如果你用高精度阶乘就惨了,这道题就是耍你……

3 楼

真没想到,你们人人都做不出来……我已经做出来了,结掉吧!
CLS
DIM n AS DOUBLE, m AS DOUBLE, q AS DOUBLE
INPUT n
m = INT(n / 10): q = n - INT(n / 10) * 10
SELECT CASE m - INT(m / 4) * 4
CASE 0 AND m > 0: s = 6
CASE 1: s = 8
CASE 2: s = 4
CASE 3: s = 2
CASE ELSE: s = 1
END SELECT
a$ = LTRIM$(STR$(s)): DIM a(a), b(b), s(s)
FOR i = 1 TO q
    b$ = LTRIM$(STR$(m * 10 + i))
    ERASE a, b, s
    GOSUB gjdmult
    j = 0
    a$ = s$
NEXT i
FOR i = LEN(a$) TO 1 STEP -1
    IF MID$(a$, i, 1) <> "0" THEN PRINT MID$(a$, i, 1): END
NEXT i
END
gjdmult:
la = LEN(a$): lb = LEN(b$): DIM a(la), b(lb), s(la + lb)
FOR k = 1 TO la: a(k) = VAL(MID$(a$, la + 1 - k, 1)): NEXT k
FOR k = 1 TO lb: b(k) = VAL(MID$(b$, lb + 1 - k, 1)): NEXT k
FOR k = 1 TO la: FOR l = 1 TO lb
    d = a(k) * b(l): v = k + l - 1
    s(v) = s(v) + d MOD 10: s(v + 1) = s(v + 1) + s(v) \ 10 + d \ 10: s(v) = s(v) MOD 10
NEXT l, k
IF s(la + lb) = 0 THEN ls = la + lb - 1 ELSE ls = la + lb
s$ = ""
FOR k = ls TO 1 STEP -1
    s$ = s$ + RTRIM$(LTRIM$(STR$(s(k))))
NEXT k
RETURN

我来回复

您尚未登录,请登录后再回复。点此登录或注册