昨天下午同事給我出了一到題目：
一筐雞蛋，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
這樣寫矢门，憋說你學過編程＝龈浮腥椒！
好了候衍，其實這是一種很經典的題目笼蛛，中國剩余定理，不了解的可以看一下基礎數論中歐幾里得算法蛉鹿，擴展歐幾里得算法
# -*- 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
