大数

1. n!有多少个0？

# 有多少个数能被5整除就有多少个0
def how_many_zero(n):
    zero = 0
    for i in range(1,n+1):
        if i % 5 == 0:
            zero += 1
    print zero

想了一下，上面的是错误答案，比如，25=5*5，可以分解为2个5，所以乘以25以后会得到2个0：）
再加上点输入判断
所以，正确的程序应该是：

def how_many_zero_2(n):
    if n <= 0:
        return False
    zero = 0
    for i in range(1,n+1):
        while i % 5 == 0:
            zero += 1
            i = i / 5
    print zero

ps. 125！除以10^31的余数：
计算125！有31个0，所以除以10^31次方余数为0。。

2.大数乘法

参考文章：大数乘法的几种算法分析及比较（2014腾讯南京笔试题）
个人认为写的挺好的

方法1.手工模拟计算

优点：通俗易懂
缺点：时间复杂度O(N^2)

如
 17
* 25 ---------
 5 35
2 14 ---------
2 19 35 ---------
4 2 5 ---------
425
关键：两个循环  a(i)*b(j) def big_number_multiply(a,b):
 """
 big number multiply
 :param a: String e.g. "222222222234567890"
 :param b: String e.g. "333334444434567890"
 :return: String a*b
 """
 res = [0]*(len(a)+len(b))
 a = a[::-1]
 b = b[::-1]
 for i in range(len(a)):
 for j in range(len(b)):
 res[i+j] = a[i] * b[j]

 # deal with carrying
 carry = 0
 for i in len(res): # 放心，不会出现下标溢出的
 if res[i] > 9:
 carry = res[i] / 10
 res[i] %= res[i]
 res[i+1] += carry

 return "".join([str(x) for x in res[::-1]])

方法2 分治算法

分治算法虽然时间复杂度降低为O(N^(log3))=O(N^1.58),
但其实现需要配 合字符串模拟加减法操作，实现较为复杂。

方法3 FFT算法

实现更复杂。。

3.大数减法

# 写的有点渣。。
def big_number_minus(minuend,subtracter):
    # 假设被减数 > 减数 ， 不然要自己判断，加负号等等
    res = []
    minuend = minuend[::-1]
    subtracter = subtracter[::-1]
    for i in range(len(subtracter)):
        tmp = int(minuend[i]) - int(subtracter[i])
        if tmp < 0:
            tmp += 10
            j = i + 1
            while int(minuend[j]) == 0:
                minuend[j] = str(9)
                j += 1
            minuend = minuend[:j]+str(int(minuend[j]) - 1) + minuend[j:]
        res.append(tmp)
    for i in range(len(subtracter),len(minuend)):
    res.append(int(minuend[i])
print "".join([str(x) for x in res[::-1]])

4.大数除法和求余

主要是如何快速做减法，主要是迅速扩大倍数