昨天下午同事給我出了一到題目：

一筐雞蛋，1個1個拿，拿完；2個2個拿，剩余1個；3個3個拿，拿完；4個4個拿，剩余1個；5個5個拿，剩余1個；6個6個拿，剩余3個；7個7個拿，拿完；8個8個拿，剩余1個；9個9拿，拿完。請問雞蛋最少多少個？

最簡答的做法就是循環(huán)，代碼如下

x=range(1,1000)
s=filter(lambda x:x %2==1 and x%3==0 
            and x%4==1 and x%5==1 
            and x%6==3 and x%7==0 
            and x%9==0 and  x%5==1 
            and x%8==1 x%9==1,x)
print s

這樣寫，憋說你學(xué)過編程??！

好了，其實(shí)這是一種很經(jīng)典的題目，中國剩余定理，不了解的可以看一下基礎(chǔ)數(shù)論中歐幾里得算法，擴(kuò)展歐幾里得算法

# -*- coding: utf-8 -*-
__author__='fanyiting'
import datetime

#求乘法逆元
def ext_euclid(a,b):
    if not b:
        return a,1,0
    else:
        g,x,y=ext_euclid(b,a%b)
        return g,y,x-y*(a/b)

#中國剩余定理，要求m兩兩互素
def cal(t,m,a):
    starttime=datetime.datetime.now()
    M=1
    result=0
    for i in m:
        M=M*i
    for i in range(t):
        Mi=M/m[i]
        G,X,Y=ext_euclid(Mi,m[i])
        result=(result+Mi*X*a[i])%M
    stoptime=datetime.datetime.now()
    print 'run time  {}'.format((stoptime-starttime))
    return result

sum=cal(4,[5,7,8,9],[1,0,1,0])  
print sum