python之斐波那契数列算法

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

它指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

测试运行时间

编写一个测试运行时间的装饰器：

import time
def show_time(func):
    def method(*args, **kwargs):
        start_time = time.time()
        f = func(*args, **kwargs)
        end_time = time.time()
        print('%s() 运行时间：%s s' % (func.__name__, end_time - start_time))
        return f
    return method

递归方式

使用递归方式查询第n位对应的数：

def func1(n):
    if n==0 or n == 1:
        return 1
    return func1(n-2) + func1(n-1)
def tm1(n):
    return func1(n)

print('func1第38位数为：', tm1(38))

运行结果：

tm1() 运行时间：16.43676447868347 s
func1第38位数为： 63245986

递归方式太慢，40往上就很慢了，不推荐使用。

斐波那契公式

使用斐波那契公式计算第n位数

import math
def func4(n):
    return 1 / math.sqrt(5)*(((1 + math.sqrt(5)) / 2) ** n - ((1 - math.sqrt(5)) / 2) ** n)

print('func4：', func4(1470))

结果：

func4() 运行时间：0.0 s
func4： 7.283601309201992e+306

速度不错，但是5开方总有小数误差，越大越不精确，且我这里查第1500位已经报too long了，也不推荐

数组方式

使用数组方式计算

def func2(n):
    lis = [1, 1]
    for i in range(2, n+1):
        lis.append(lis[-2]+lis[-1])
    return lis[n]
print('func2：', func2(200000))

输出结果：

func2() 运行时间：5.747527360916138 s
func2： 24409148740351548599925498715321240869628860756907252872262647838734647931230342868686956144292834055751908948248522484525867447539951646983758606354478955674745609912757486896696189527768877637913625965661670590581721083397465020857875171654433694401235439049521663864777388137542208542606932420146722104150538432242123310184560891979238724675980880631830363951045382347095517766545103177346564898780628553142656234516057031340827419700527132984055756094423862466557226645971773078499305224288739173048649474311666101005308008383009881921730435536194212817877253003833362370229404758799238896482250033623269278847131408963307723882513532872960047538356354556564396226450632779174848341962846787788811178798497602855514966641948235339264458394412452654984045299274192466918129326084499219335274821883726668423195930431592883795395103204269787516205387914357878824253905413202609403589806501620250082023177276697171561509752201690814075215060297763914849372454603602812537487185186880850478210470234981248602666813595161907654281522012103921860291228461449833800445309641766676001925453820413937018308001901803554248995170466065835041204573934831059016212268847985492202341578798483501160922528110750941675136230461827961904358187816123614185151653512299104416424248274778327834821477031376325325413343209808495886501022859830416858882580466818087619072302206840619908663667883940045429877920672727695280218733251226007443194083263469107322430018076817595273620094249712799807936546951954493552967041442182771873530870421034439649461783385538781835310046802901588546637190984845851437291477877760618072878532032980789153762808546099904968102340070705870755703348675049119218343576746235151582737574557320633622494710630247963577932304678076229138090308255374631195343149565215090770773971055390192673066959582821508014098936838504869979949768404087161416736073623322134163991431041440976345469917384007322631486091888874259367373693887937789321838226495973454525933171777894902851518060664360905131315902706996506455969408863129498431581249108844916653011000172152347963967972902989525267895423130506854974482520665985952841281287902714348258857036487856418688933307647118150981862591797063729479362129176268890799714434784369256156969308509902234643771745067307168669130340149572197804631571860442823590045740890820091734495450991056809908768657391697126531371353158269808421531780505026107034561987270880830054408188794505521440224854873668985907452122564470576827479506544298698494854301597116288733398432010735198937178007356109018957905496234831124367306484746667906680731612356288472690129059626375386495947903323405477158680004849750791523003062607901136332115645505497599063376340821188180591963150139507385376783855849037532211737081164362657587023781922829724404326695255741367480744010967116515510514972557476392545812862157213815318943216649697962221140854545888067212739680918290079499723241653802785109892871852082050976224597336430713400533659945369744631044261735640583719969718803118374863614762429958491402401550716634812750312670519610918874518166306715376480370475197516211192137269316188331194790645607774534059241069627284497590469378938682183540983569514375294583880070793711689917259732944043865258738449874028034653076549457084388752744094229532320356382181575341613251936696454161345236372401062180343293561069464515436201528534878529283073928455420262194841245618055657197563338869442051895469041823464131600211770640656476638528583438430161583974754025772944634687972820470807267923083204715468686084534306152764217127235716820384938447294784569468531605280343606586135464467971732765655674756992722541279614628828732349931755331497169138548508902415456951968116201887847478932383589462008134452949224527172366919638689138933517477070699779791900130633484102866111867800300670837673735404042976537604690366136750584829592534248473650540860956078629566655625602050080842680449516793552198349686959945114079240721744668008191795729993864573249888988775009031029687762105389425518283761494479380337095186339859398438021046915251594974385429530145672979739910971670270696169675835539313573677855172578512697339054435002405142975257198363313404484960122975027183010829836209702216598373116964373381567228885176952317826690787846357168734677392746838483925567013994210162127095365550435359559278919414820528034129081341649125741980947389118459489967304942515125877350038568889984108205374029348707174211758439154920761076605498022095446559821476197445777290710758599620985070498504478521016502314863395799906926403271167802870397616830970151922752717041101524557390061831409035164019306529693647549063346458257864979943523084719641700657926592168623360869817676665891180424720196271726337572848938972206632378130228144994114455568713996617694950192874449045310410293939475530601579636625790638996885494824619411615779453679767803053787115002070151852694050157141657455196268273380282279998383759757147553287162015266408756979542933158428823556578080549453335237465395150003238188725517035251371005810024536273811193988477180571883250820615579536208448613208546608588136755989016990891959941434085878958186930205806652172739181272116184942523731512074148353585910025514590996028372489199473925073610310909055531141603318591398199480754145778523204401130916152151635739190529700948046136363064838600233262065807136064585086469514859139794046793536552543541888112829030068075481447022510503601290724978610397117752620661366392578491751667042120831662058596772368265214775074311414017862962888317972335661666588106830383522080047364755659273125965326050784521232333028963301506670543331739504530802977052710244619438599010337004075902055354701064750043352771631625749307085287659056792366350025383605209219845599266146000762150846774072480610873460712160773767239259466774724589705155887181035913934697527787011511034330508195071230631732890620385090074502926935982694474742314617672548993868400572794836072319047903396862603749047745086831108344010351162933209280472451667550486074163744433562808025797574970757956197970513455615972949282822909045308500391026951819165785575137833045335831542913390521452096862590623588743885068739462288738180078238509459003108451388058425185325255278598248476414989454687566704499533564136507854998532695962990389727874647216484637087698764777306158332132305419102928547205094913155793009665804374908906520389307567988850097353576412645927683057065557498085896783116630216676543608905484100913981268855259535480872381224280687966654524589486788196061983965952389047482866143199973013424262574693770045613772351089333576494011662267514488334796099936808644724752126541897046371598256737493120102752774683778857138341560162009549654511406687057103116893158263564481271574726397073421884336372686137120040097072635137460823666568186932058798492296803191356632466959505189786642631954048600285832789372824485489452578531568801548629738762161156311764657099700842049225616764476262143797188775599527520598278801236197787705607731407171445772297698106642266137021930291717191339967114644145233422140436059693521880866916423176343086702875902951236458235976888290371909803727020811490234227532303770293614576019326045828612382380020350987316476172885874409236952912015492698831226132644623733247425810179216162391318405176059854613628238748043758887836020685470349056358479560022649944011893428269693159726026171649590500425355279439669913273829719207102094239299086805320200288237003938784907403835166708897329115306160716864431820503783972188493242365222351142503513199679651678948975212389769950071956417214435322251661646712709399159141911131043403032647797177203515710766179441724976436870496812733330477663506905277753941213007122692533193009677271561225037592309131090467954895317443285837665105418380732878002415067494919344421219038234796748631232434635399171932249906459869256353597473893928533841693353637157240987149545909245234433892015860050409613787295137944536956131765138868151118904328301887115393823145000464471963398632564955268281809055052904296638857344056206641957249299023373636603365053861746236863158339158370168168707687528226017155418847783785459357224242229897054291234159521006599354068779933965429560197067874136535813087505363456494427932135964326476092449759220871173202594694778860808899835944628769203020568675451480734396023113191765254340007796688104464466391980752274432992768851265353612594319196117931815259307086848548835468809812705217362146198289234558830376061125752058468738136926348465795381341815844701442623565740026992403133742234993459861383688346279101699494111462651580821635947183539502676098829135302126435018687026528361412751426072402946491780915562708043777143993686538236634997127428300437940966255227314994361532561941848396222248411372816980506661773108461491513347847416828121930301289555801492155394583046899976402494067967562614434663902251093217610738155364952933477871897048506825080019583651518715138986754490886220229097721579204659419355073941199392514798748846528776775918720175837972015617719193558939347075601445238900601621651624111812286575539915211447733566225870032352125279298924370157163673831876693607635642624748026233221520217958110838168756842845395385460057865303892717137908564643381552793688834434031090002694689992388134549318081233893236680563979645734737489759163590109776500938391213947742709333631086125139431901637731762675714723739222377606309827103462296407515128270241569629886599598512694861082608981937303617862482923966088482525690211587245386204102751305180172582816103680260526032826270349498262865058494919415338273350207299014753920021301571858838197582223211016194367803128385332296390094950446213019853116711686073440799435291508524039130458427728944889054819361371606534235526337455365431932981265304438854045299042731775112167720156523637344780956085430538828913434629517436324802809626739381881771878682296119350902868602946318241014087805609543240143822358555790183560048010749622618942659304217153581755599126510422028682261712333575754126858821140426421215899681887549982183898311389868664238722422662642236949651649579689706464936473546944126898264780443788404352352409318426204681223069335705061367828896354942378737381479444062964229899455463164267512970129927623409481050237009501415856372934106683225617300302403106258704317308895220474935327528266213636964747381485803211473489204694259620760327081956720793094170857394447802485025709895888909033129835242683172103512197558174085767823177800860106067830369512953795684197980272076075713048409937344677267670337808901240085047653399688922124169053845146025600955277898469837620224108145920334782121583703428595684765084272130983513164325011967195077207866031368801283019447826784739118801430244989447270933004433164701771567948700016161300856419414030621559088531185523751431230664981078661691803077611008194076077125341704233433851712240837914788743717179020527146124059551136565906406474319598485868518385811228164511717576948106689005285887622173934048509692611121235095341320938998782210423780320768092444484397696636843651458380614585293191100861292373822056603394241008052689114478922863913463896454624706713918535784491165602189241857298714139380930735061070130312948514299617739992595507974462287336930250549092962531858214587498472548455440201320775514767585469280357909100063800946288412064342294415616378571770717754089790831393376468276110407569197195903018674923587730913931655053566446189399064661351567865726625657463780252805416220656213729798141084706012166883816268119429159960098471356919796892010443012750853552711118340980138342541064648137650511832122517201219048328452346476242904260708376045057110453256085099713164270697904442625493532168248003307587048852634882158825393774983014076483122501817473534808862975143889639123177996013200165382852020839354022939404029327055441189358046566393960743140154595136338603190208680113656508357210677329200448583687910315127423181568681929076135424030985740320883554604901415673595162708231078541737532225113047710132504215997529947106507579326964937283399641724907744019014301530178810090480081523461456026759112070760913070274689472350546906516216145177998332312560779525077668776579485090852847998898572294905154375014597451610666969753085548001437099092982092810978029102884851163963901349207528751176206757995408545156884160937638838993505113184381833712215841907692128413653047609775533129500367726332128385185427738919385117482900929228074986980963876865563041057176097397368673187210581100453275176365368360873566754438647191826842260602407596697143547323396662768578657974967974911251657925620552069521093347709739291973209949906567376965443427856352786535750251544991603663532318503788562712723949882471813468772497950526153655557946070499513149254723474006519310694716954753347201963688414483265755924475576053616447778928285598833943425807901188235848945139310663659301568148122369958578288853197352690116264501564582068500712593628760079772116491488443229744217117816610524253393287517298475892249524914493125250176519082761989446210384509801174279841750335286116390518069853286485744384142772379541257645633857545490183812524302202130840409925585337521144314432548225452472424370038107403717234566885315400254012659816210810364125913602135978074438874223196924499841630499915163150709726757707617393132955503264647263327973191914588940560883373907548757248795363475780073206934588596395149402397209269611026438700911043619169251564104077949805045367152829632453494635842410244917189250570829435150900065266386152850494996860352529682221925388734614370449522395170593397769358373516115881776414220699145081783524243906095872276277714122136053930770105356582341073309513331399960016229057786278446741527289083075150233959022134555673942107665377844630393369179637782562766536333562661668849777385108009169081893846357953308022150346554930819562602879738544519589101982347121907375403855257646196026301327776563832036317634474827116268459662642944372126492560809693405215128533542180516869398414657005404853959478784610283012801393299293310865488872758552276793538074504133040242591906704068444956285933591466141684443944995600452747509121161174263925961586725949935622868399359029839107827074905841781076498539527310686370526270681865655693009059223545490805954994590675709430788102755649173896750556906646154418641141547606444645526763134042282137473184008596795323642631033605092316973843824408197641392905701384703345135512132687193112226785931834642722214013816407866456173040116225966931060752528817503177650179914126707589660248124031190071809365166978341644106964243033469769887048575508386784955140432020233924784355446210637197822991107765127612448240362085627822400666946273304328848922276811450605165921389225141233422336099106206377772517192734767594787829240473833686931824589417830653322951907841548597844096062873417630697698774853985065133335227825823113657545334175514611979721076701165138900954236795191146361805163842665077441931079741545570744572037028633851538399950721772672075142872360202094192221397972505165325107785034835706872638848656149026274423036411806608044823555265744646257249206512834386660143020423948785596184806093995850873873705494493818670996970385982557637058170558158538881493960127942681491563288087129868402873995036883178707817721883664109845503482158347470367071504517994951048418251293133173029776520046255207899574198921565314103334231554721980617724793137727610935226936253606136685733143656166643574693542162678622050799264525351317839164439485777138743259069324372629669549621108339529976468516520015224801500355289589137222571896594487380009542375400079756988912528537356678447673465842489263718944244233924704334635762958028181824566762043052765223758806396405486452645302431561032611065873987034847505102238012754129874094467780980298416821752619446329268236516474144175708219881394903032449192195182580559924040685348692431389253803563539925406463174242114362049832246442217588396004494777828071687120120375069596432112854292699567839530296498454348118332634927722830229588839339570655616430436155013228768840316267878485046874747305386736749195380455622328003231809915070107114309555701413184332132608728836736897197314790626631307232994943375724507785356491489246029758514005038238792652337215117716485840289381142058699561982438030467314419644202239189997908931023160640465275058094730867266773583302405941675221662246210217512164481492654454879303375259389632098899214824416521022214849557729662120397204768947825849174850508878396693175010383044792529758481763036202051064359312534435345352058899051522796027156263773866885738023997690186661560052625102451990781835273033110092027070354997644292672163863298533713947403734908010236269050338802683544347298738352839853015472527853175509756805140645374002004613851208846431250141112629207146125675429340000752271125971050066837694436639563488707662607683969584640728112239220363816369021288461452486605865560773665796828227446394865332209130937048504260557876307952096021028996288738329886357038385284310866267895231680835169748191967367697430211656127617821096335172769801667206164891456908590289003494484056995806637066992955415958159314171163404614333429897401069300697476301427883200061940022481255981604527364960339485161222448407205404984477430984370308229323155973833766946345285824028326119032388823828672834441960992688450359314667682688304180295452619332602293365217713170316995944636546105729451022872106428307563566284729979360785706906555551803638271492441673212654042379223576137171408067080659385185151385595560111308256669043786003714798047531117840316835962650303004957436963236811540955510015317858745831233362798345365698586947859145108443351462431860271105279973152935998328835390869279319586484867498745878696431279036950665441117911387727781410600568530535982662469084210177949994322966378363207354585673167124899343903526773338625544983200511244976770388307383072328040834008614593594879621475094721804895175527325306487395120233551874297002725091701883836027953564203996350969289523471530478723626337987799390002975648934727481875154605796434219841815582376368146516683715113454434371648867236779373118693337941628654850340591787823202101444032772313472289252120767646405291275392183173528686090110316840985399248893969988196153180254475271531366684756953920772587167190011395604552046544338286263393538857573354044821445543927635917860659927013384800944180447365723058433882419906249236302952313182353909167176982872083418311771529885230251325580515092060921555981644873863822676838263757003632261125673261277695545269346542445966077696503567442261411971086185999213941477602241480935727231470209141610733274182521339118675637862373733759175308766114140729600379714002845630583515603150771959329869603283913942529544279013356897957221762234098821148504282355089805964782003048351969885424734614427500154894193046266249197593003531850357285915345056364291401377916113256838622836495258604855474926656285454681854633153653373959910297479501710279858035183488962737279895264362254092493666300664095345472695934889102300312673329168321423342568527727061704752377281353028501265624161606861953175557055821494178213187845873229236636907218541143222634270146197932997594234132507923292388410341105176667449689246919739170561473327373066399865092028914990696304817250443891096975109855001492877557426940503540679001657580150482609725948751420511145152987483170045242631966350698725968910983070865767127849830737412322126040484691714575668142479891732368330571001427055020055935578672890353653441848859744270133371725900393144942080089343024461826955088952253238859128013565280185248500986212215825418406523557278662867125959681080100512968984461268327086239506987243788027086395683224165760381088043052056711601945105725168591922884944886144019073865826560830912793704925643553615293114431953986472885073481804813965020095371346303331532592201477387354850253085416761375904098132857967522121676203098996469049739801496078263390836745879271004689435525099903715028998452601013183948508034553199600759309882444671164196763130657909535936175771144599102995643590511374804474762516945803632631257197274070144200862637603117874097530150089307163220298814927262718454417011178475652398089753568392016350930994717130847744636434098765218172478822258643890632342550610086267995749491110453175701532367199945101063381021148963923106118335951826560072843596679721632004611593089462338333577165079958153367932766450502734722198303174401271807015439400406744382083745639705591746344936151896831296091019583485256037431867538371594717212876330684158134093910584621041310378713815524782346452197620015195334163677876071848619823451179941042981754911376903897776139653908335453474583971528250255193492710278561172146942988756848431749819971930973913887524620972345935071530636910426877740260814910924258793755468129755277638735928276998386556296159317870400052160229139012031104324471731041021915655888512550048435796785436406625118110749426034007708027021036992381905504364885911758907154468389571198875828130529830606308533023573496472423128476617996423422316610654644481577962341190249017363168651556610738170467746818135458619408001525482068376132088015325785343256772123534690404220351237231531530765067671565560010115560292866712642312483895820442429846085668751501144936589251454675845282093594456454202959646904534864579458605957260176808723584588723835357746693959887150301347893253867486883127945791206228429988048706863020350549317874658623140726034107289492030166558155624006311383730986218621588921993437478474886755815796686080509313174285144315569652792475213442737485003373238351149521858847350401186378093161688926712136408812096973490559674027832515346906240358167855304729107711526352011721825569644779301251083837024924769212160392384156118203882752393998658999880095788678957507638217014706434024987700407431460897393349479363584540255146273392573607269860736911900454632286557517900696710173244733710564772402765306440649948029653725363769109465580674274391414911620026085347446139236111948242849389448643877363757828377562048979931359521727800886595281018231692448999722297214952625399856644897530636266033328350290902018968554180811909523686117753374165797428999743763089130330827939747127880882459377275126585030770747941824303564232447957707592698881940617362932787238610411182478987403040846212668111178768461057242277170797840272708270691849186118068106963643616994540855697649799272752887233450691312572311275641758118688372521250650184447459793979237592356874310192164257944343904378495164548945990336242430066757649211219031305881888259496747940653297932337678984810923667225694315944912140349846990186754843567576239146937540586092728879986241731500975537734751684288525794567672605823809432403194193862940577524423683008018402991533323768434450233137888002009449942864706932684286093944014041183275647972344406729145236814481048118106659386141446623648058612983874791233807040149306844774894080710816740778226546204329627087313190119775719405647184044352102153494299931197933215183243489010540415779014688492548926944081194796929695467715446575527212623117512230725856218089431209018900450376450180491403790309474636275933708058850046485210562972391758947856772989935773570823073818642843335446899326039733647952949504687354867192829182241845911757377430023502068278402429385974659794520919747917003580602564982375673624209920124359580583763203230193900355923068115528108856713926894446315737551971550515509272256910542419159310515723009481918992564348444814210510465146343124563762477418600542521706685648477494795797224890893381926559219697931120651362602857716645573270256057470179931222903832682118005439916745193160536191001846176574122529801727155901025016841217922169656190317437691475079582400575757297585273175098410095719024631453261673723579239688672337153085616644061409217236837159226821806406990317531511689779819888279486495763096100906152624248400057698760202973420315148817654762003924616740547117269477132989942145741050613012850430555685434598415345777361464410252420389236304481363760199309611042799127947441950132736872124059925645805119254579066442906115828949886290255640494770239825110581945379800128652772427705447651500814019481382020284903497885250616903319389667910155222816267959518210524036403274694574534135962384353104442345923411705799984096019267313833970587138189908156748013850458741015389617937418355154837809766185159125339464879318001691155209542550022669618811916922969889840454122742203823968463358032058244469919329638251335419585670798871206586356382281785383757187086108571832424576880304013529595880557931221618225194438440455453108809509300305041816746713681989292065094862916900937204416848166379322290433498825902987414495564344445638996040064913087930959633758939052386340910314557717344405794785347712603151327179435149107409658908395239671949207116945014217275558872483652954941410560867023734321135477058948014665104202948513260741841568164553750317600841520174275354091427766873073119812931146971816777327261784787546399196144597581168456665175668494504965150245823000050274979320420568105482646108749979842135774736641575641055164775582187360300022345737059680935625713940942871471715155101714677895904826519976150762226699986646316491136674116064067447932118073336015256834651762368029891928647888729423563074401222633948630509128712376858470822344584001341734443385422027532922316931210739862275633582722673708957546302524299670124810298157311113547896431790703584696591154771207839539220097675835591363869036015595908583325236634932671746905030868213041931415874618420312245193399063709435773758516563690906407282404723449888563661688771437874019159971222320389106027480220057859380427899096274862929076587727921980674198842018889625851321345238457148675678844813638901676865572528422351135828376398886256522321836434582354017587677687781228789258031765955344933692496062551695282452461480728388081711548078718170267642629210512979896414454930865847559086855524569367272610106556526218192322803176147940498958224952152753642420667246824641849599722195112181014229644762080430129852948662247473436653640452736379680646438142022861646067106126041945991399115608456383425532157483529756370925916958322319489847118323546161948232784522590485151641698752378252867979161626904602134595815072812855353359254466860194732523848229725175422910689553216185295665216006688437409286651439664942023252816656192258285352976890840618984088603152059678892707310616542288174436495883212918404837716541322622109293823328022940925967434703364679892210881663459147269919549887245614824812272159920115132986626216724285706857039169184753686821191533953919858992912606244930146960063666220303182535126926437459896204433585012656240412982874796185290018797922386009987191507608731102359434438523742958852631244132389014458257570439926898354357297023455383944765878584254008231513415393725876992566643375822931045280067181472086400359467419063950683574771513987700003829829776408535627617476830428960938814385613954598844226605459152173281769347893981974099747424761564525283764817795149236172324470607034501910188990624086972258937483267812565555007110544311776526800837317342012820504872128685549480211620540688470849093264570013432891650134926078901319778297177811038144772920034440600991143200639056204494155533145103384275354119539519008531668610914691528185135561205236240068221246259276261570690243265429901836706422383472932138526846862352240719179540677716165694419647097631446423044625489844565712067349225941905050861334256730647111338373120887064661403743361948458795425010522343087066307752115846799760052415879428819382579366648646654924742046074517891401180632381838757725982920516495794829035068224410196252940010650297748544222372693798802905537259492987551923324433158782772796261622483905101049320161051351867360739283421474651422066607804468396917112202702330950096031028825227484177333221931059397871821406632025749822956164361602573234722047828817211395968986875617502278060327828286081653729711213868206271517054813197729004075530598655185275487474155101615311068905396919663076137425298568843586568569568433211924652868856395124083487130992239429822404450674182852466904890463589797897194181531462772512607825202362429206445574144563789586374093307255204773779443752924800375140981928523318411713963600776445562538527344452941715402506423992707182125252313945311480264634867227680236009916653107869282661837563038215685636595455570684100088557092406834669212984707495893847672154394756845242398146429805064541736447400747913528239751923284731321423871807759270457168214745008882328713606445492615162031995159611015853231025367627658487894561726726731673500254724225628628576642617362170689423274793203028357297992893687970679461275517213250882975012845913794200596259166294947398622591172886273044600825253143225974708777975623510467075214407125905421256990103836124429346701482832847596100706262009287167400026237488722063592102429347045967402755225495826741202676783543964251988952346320064429703358534237254936043730331228060772134806008177514169380836280061645813745104174279406300978462029201099923484554850490150424910443299730110462574081168869971460038276799116773489613323124989265280423779191349349656655166663322231978125109359891732824635041336580587480582426070900675063513566607276866973438868238342509035073764785371737954426020161180343892364180304979749896032850254792675783551524421232529798775900109720514140062830155076261043792346540209542115080973584089090732382705529626791449334787006392257329704710270642902308896704897165828379363884137473997041442118884338324415455914418014453992824917243498874072400691017444493437782434688405293105104102024353396622050959459569586319018711318986171512173915456435267490788048600878769889033899957229635746516129916704924506246426753434054844468295809019388589627676611876158928437353583002534978637940748849142398733669277107890636933841846811882375304995164459788819835570765883750119639710600830375163801254549204827601988425776976674401384520353131949298450391652394019213630188798487013648018097456520055234432212767984232234481337107979455612247916389370598361255121144600597463949700808832185824734822057575329708642861329380983941444464768382636353134078933965084605030451555153046264478271224837739629041540641764895240453183799894680392291834703174365109013573645808494613083608845846374424872357563204696041057511046544081029604851950678519813852742613552080252622426718297524904709319401048684194892723217828389193744279438630083503735019515955420381997708171460727094463363222672823156522382303812128058542235793487080541630556045843728499394180264034532388616781357757267291412038356233675728490905111467755740568758854188954414682163424265740888805592558496215161520115694833951172794540984640603291277626324299463557974888956421922804564523931496765856294465448228667399649207957268169048839838957118871482955094999005350709904192954603535539893696101867992233024374486536503689827901017455938533399373166111674139570332159076655065469843273231051286856796743312428997433580753577839428494457847627792586465725936176583569151042418020459331852745785274644429420731202718551189305546577789296441606690007920768355215870259926494649112589996469650800754416481430254693121270595188503952053075466588468143358210434012164240253824722325082320375075404492922782091629577164909360807206658894727762460275512149077848094741906738579041450136440856812030706455914620341699824190168930972406213446345383166937118575507976651682839873924082330169966748566432124392462497202943066041770236604770890445131904097091127901263388086483196095505187293766649487851436688885738426577151225944624429803161937456053029345185017717813771820614307675255375576043601596934973962542877563218541861261437891262099737971315096484619046117300048695265862919676613680694724939997030432865349625204915779116169074497484282573179449046724208161019985107100113656817707302440792544551594401000059338838005883304929131103197131649036434379146094476588910409538434925570035799577979663945272071399922929670550575632159993439408420986173236316292816828151382959329384252578975119294168254741499426258707793576535447254931346528059432008163358304686795262474411390598080216976477674519101891550561094256370298373361726000243367863039863488319516916775596639455513675220440331595294807902729876005247398029458123064079684418890030333664437620857087250490696767347531788528423591833679935806111051280114406324494487589745890541199672288320157346464831732618506431180605212170739478360880558324292703138109815438492619437833216130760078900279499844875167797881465558836026390592095581238411836359229456863824227164729855651748640545767979857449048839337956241707701768714021439720492139174972328288083163995880886842048792708709392585624574517593969225558313020969451526245153873753254303385407003246150835037197880673216479766437839700351636906024820379301075775897541680346318998379217133761687085027096449907994453928737949393702461756326609506495790680221223433674697876500424113998107125079599962190157622028664455754488154298611155738210623601093229671123795986922624643690839433770639174983557041206087267828423328992399952301746065244665758326285625966716028926706751042645893268271717309461135720903205456290021397486896475533546378604243292576105540192111074327213800769487212273285780737497292986614786023201539591851548112764658473759975964195782172099729930984220977120511924122046240025926790957687729359496040871387892316977677719318827834940916556484090406536004578889811807914309875112916212105055494436844503423596298253924021969659987064191367876100052585825969730424346397037681261760216722837631277802449073168752048773983573090722980710219858196892584339833930801608107191005859197049311496623801920039819976493764836055962453375901417792957133639585868185220203340858200960561702194376231430521254018886777984401562276320914846679986976676949003948187919901995337563702808925249445427862020161413454736837250333094786908792207842009324025935773653368810957145265586881093258927667282786556041214983779050291701014048688696361449622442129583120710859686046198049003061677592867396857175580353880391682454871306449654674601724904807806340902264189189757519604589575912682817954077116071763825007426994473485419891090427930828722424410725670815099546902618019409849779912954882751054376861405184778929591653098125924837587334486387716357496387582998678107259659116625012322804364237712243211738871730527200748023396514495874104219878083777142282472952024577444483435616019683826833739819834205667649290663673248073172015767234982474275332774423930842754947940009682551800694340246806700050291868760567206410908821862194381759965019066757547874745292254951122829139278036127894283216815197910512907478028887203249495373665586864311453504715222369438176133773678774607657650850665936446991740878516391212398345093321007504972539314298470499168765821850127233592937828433849397175543611290627124305033188770858462021101938923541812213484707653707307837267030409867814528461826680121163977111066309643891376960366476374951488231501608637076943671090712341255950229948060216662606600206341080030486980287717480462269165350479956621373574324304571037070803583552952156156361804729959389155640950096320610702222388015714001798559413434399400531987729069175149013202582418531926470307055725309377546073043705660926572374497847233834570077574220804826019480890772292390157505662955769281208339479738492985731787455386358515035348693096344852863038502354930544053879520152136584849934125354994189448706407475085649221631367537536021953038991545562933190933722643125635809582825415821497396679916657714704507107286945920805473874307266071294177497491611786795712628803692597784618461395207537887899055233088915898917817740055223566054666315337560052895414242335649071852158006731626924336823043052071579359085015118007658684520532749185032985333017973257108348347809511022369878753378058519500200679973727085751693733206210741265961073062692681033276066438022300657538240776161920916725269284180784364919233201271797961406815365670452183026851949831024895632652256712275899469870550917507862788008653501048106363552653415483604758459418628766045929763439704846536984490843236111545092763700976444190569328406391568720769234545483742542135209148285636302219922545043857137416083730062177172245716612546520815286809310191445625898524724067813097848506491373720645532282888914542784969423909811620086229008565841479830928839947774940040430431275746371746697947117853607010807238096947841320052041437753237625919741137828513913623306072016987281675629788086757732874709921589537747992479010468677181839796193645160135483126875385456580776086034632369714840773089806096745371939728880659955201650864986838467746002383929026835895638255817806640941138751904088565002855640154565458392323914130877665548060765601418049471292531346011046601418737632120300821278391210416662307417017833839297136754451675748688016029071411700696058001599156640556967834585813298511044904447653642227080767111707128250464912806439099285648571919469050735021019237762179530738300806094247893174447612691315810958579757931742846943482888584510997904016735710330245168898467969067514828164290782012880061507560860150688411705278694880700328220323457028828682623807946542585746467206457197829365502237477137060559619193807276533539427351789407858172064971895048747225496045882288220436749083843481109278145639930657610963355109987375554419096714438439033471097165839780055957825942116985287959225632130653257256419329979051762268634787647514786117945494583428118477660433468072596545770331998227698182788815406584495795695332440562742025975989384919091768677908625297588867492199417382930453819076165151687424140453689637557101993254541798414719432927606004151018654865554198624686289291637091184380562278991460214885744241966811973436899478496395264449064016174917390825768274832593605574239359338208690420518537049995637192446814241336495227950582555539551890294201492514363236038377617402111851642594868123860455500754084546444613807400306925434949226443833618166318476711389841118426314797874300575590386094946019272761757843736276312387050992906322126784548090450911450017308053959897336924284063865215428259606556144629717658891686787249442304913700541497520919796748201852013170520584990765801627351129448514665684816877393834731336255576944281987992782633532212625352659384760109685916173134503758563860471976075193468677361786155061147855621624244463176758308158311399143582977716435710215158248648950457608826668591389490009440491289245332733977645804651146440216727193338913861467015344572839347627703315044430303135578966684740618105606429596513411036614009249461775227226559054737017202178245195651672549736346928234745730617347245132957433219303641444063992881141481499647141723709886428335526533212844367481223739331227705955284791964897561493859619794430621600950256403797800377346267915762238696255633189601116096547319221831318502323882897580355706905463626149337517805972655955511837576737971982602900278290418707637246287852109050295850559710831822637004600128434224441772957503987334020330774314862422085199446727633663855965164593810122084595440669611448886464011607624720488831033394767806663291266431919652661488807644497906180787089069787635797740920086998371785972771753250350667649284813784118184383474932680302495131979263882700148984342416925219870915610618648205482351526661392605602704000545340683999340871315037511217906131407579455540770712203556083023666799224567752832755181792998703544709956716814681772300468795668398675731469861437285960690668250076807285779835299117554345744943836226269921774813859554569236386963698189338550822604671615127464800251087186417561879721542571675892214709766885395722955142716943330285085015301945768178557071516205595851767610815066752828736822128288786538421595583651545376255416893483982256452753722511290183109524226877827689850056446463684842154075270181162370550941150988383683712995827582559493222074307772118456958192856168889305185261068499089972461317429848097025681983074153815885390284774287570300310380207405757351610535566305269206357772540827190350313419555834552645946643985671627087350084684321080416887426015717743233833568465958247901661535964904981068056701897041846144945438569262719155239241430206165477159440963695863495492293821692181558434747753541950844653528892018677908177099539996497455235515060231980619466665881443083708056444177126081738353027432635923090150167650087624396738581858787500108728102608909103095882589312266975153696779162739223128279432921942405114611612854790007735011068406370115571526636363702607176401926582753564383509690318848750282066307416472272767131309503408382599914617610446713916460357537631793387728284183531000095374017390159689528458957394114671583514688912365973081598336189266108893786331803907013976755752742163834183313284555853676905184974531863215845810346270377628235743521504380000074770761168706708606365991977471840574877897685367081047225155179797069825339477263786863948096090764656148220237541799394587116112470592877496661805156449658939676171045033818321418891921670736629059167804428484162727089807834332977562062033186793045623044831984047550444682640090720289669441178027027606528033915013284729771294858173104117672046440835306623458065988377912656415379773966316677492225169477905098629489572163008675692330318903549250713251201381141907811605547758387703457814846162980271816830910858974989659785008119514272538449032070953146814256269595334359236673031393848712206712516022956379136600589842498781668797694182249717433632261774563882424489609218834153842519132048606912185402806574501863481298264329013597490132366160877587177610016114562728265762135519452120395645958649890445358473096210733063081797282045886922228569646222486286143590626

第200000位，这个数字已经够大了，我这里100万直接电脑就挂了，但是计算时间也只用了5秒，足见其强悍

变量方式

这种方式有点类似数组方式

def func3(n):
    a = 1
    b = 1
    c = 0
    for i in range(2, n+1):
        c = a+b
        a = b
        b = c
    return c
print('func3：', func3(200000))

计算结果：

func3() 运行时间：0.5715639591217041 s
func3： 24409148740351548599925498715321240869628860756907252872262647838734647931230342868686956144292834055751908948248522484525867447539951646983758606354478955674745609912757486896696189527768877637913625965661670590581721083397465020857875171654433694401235439049521663864777388137542208542606932420146722104150538432242123310184560891979238724675980880631830363951045382347095517766545103177346564898780628553142656234516057031340827419700527132984055756094423862466557226645971773078499305224288739173048649474311666101005308008383009881921730435536194212817877253003833362370229404758799238896482250033623269278847131408963307723882513532872960047538356354556564396226450632779174848341962846787788811178798497602855514966641948235339264458394412452654984045299274192466918129326084499219335274821883726668423195930431592883795395103204269787516205387914357878824253905413202609403589806501620250082023177276697171561509752201690814075215060297763914849372454603602812537487185186880850478210470234981248602666813595161907654281522012103921860291228461449833800445309641766676001925453820413937018308001901803554248995170466065835041204573934831059016212268847985492202341578798483501160922528110750941675136230461827961904358187816123614185151653512299104416424248274778327834821477031376325325413343209808495886501022859830416858882580466818087619072302206840619908663667883940045429877920672727695280218733251226007443194083263469107322430018076817595273620094249712799807936546951954493552967041442182771873530870421034439649461783385538781835310046802901588546637190984845851437291477877760618072878532032980789153762808546099904968102340070705870755703348675049119218343576746235151582737574557320633622494710630247963577932304678076229138090308255374631195343149565215090770773971055390192673066959582821508014098936838504869979949768404087161416736073623322134163991431041440976345469917384007322631486091888874259367373693887937789321838226495973454525933171777894902851518060664360905131315902706996506455969408863129498431581249108844916653011000172152347963967972902989525267895423130506854974482520665985952841281287902714348258857036487856418688933307647118150981862591797063729479362129176268890799714434784369256156969308509902234643771745067307168669130340149572197804631571860442823590045740890820091734495450991056809908768657391697126531371353158269808421531780505026107034561987270880830054408188794505521440224854873668985907452122564470576827479506544298698494854301597116288733398432010735198937178007356109018957905496234831124367306484746667906680731612356288472690129059626375386495947903323405477158680004849750791523003062607901136332115645505497599063376340821188180591963150139507385376783855849037532211737081164362657587023781922829724404326695255741367480744010967116515510514972557476392545812862157213815318943216649697962221140854545888067212739680918290079499723241653802785109892871852082050976224597336430713400533659945369744631044261735640583719969718803118374863614762429958491402401550716634812750312670519610918874518166306715376480370475197516211192137269316188331194790645607774534059241069627284497590469378938682183540983569514375294583880070793711689917259732944043865258738449874028034653076549457084388752744094229532320356382181575341613251936696454161345236372401062180343293561069464515436201528534878529283073928455420262194841245618055657197563338869442051895469041823464131600211770640656476638528583438430161583974754025772944634687972820470807267923083204715468686084534306152764217127235716820384938447294784569468531605280343606586135464467971732765655674756992722541279614628828732349931755331497169138548508902415456951968116201887847478932383589462008134452949224527172366919638689138933517477070699779791900130633484102866111867800300670837673735404042976537604690366136750584829592534248473650540860956078629566655625602050080842680449516793552198349686959945114079240721744668008191795729993864573249888988775009031029687762105389425518283761494479380337095186339859398438021046915251594974385429530145672979739910971670270696169675835539313573677855172578512697339054435002405142975257198363313404484960122975027183010829836209702216598373116964373381567228885176952317826690787846357168734677392746838483925567013994210162127095365550435359559278919414820528034129081341649125741980947389118459489967304942515125877350038568889984108205374029348707174211758439154920761076605498022095446559821476197445777290710758599620985070498504478521016502314863395799906926403271167802870397616830970151922752717041101524557390061831409035164019306529693647549063346458257864979943523084719641700657926592168623360869817676665891180424720196271726337572848938972206632378130228144994114455568713996617694950192874449045310410293939475530601579636625790638996885494824619411615779453679767803053787115002070151852694050157141657455196268273380282279998383759757147553287162015266408756979542933158428823556578080549453335237465395150003238188725517035251371005810024536273811193988477180571883250820615579536208448613208546608588136755989016990891959941434085878958186930205806652172739181272116184942523731512074148353585910025514590996028372489199473925073610310909055531141603318591398199480754145778523204401130916152151635739190529700948046136363064838600233262065807136064585086469514859139794046793536552543541888112829030068075481447022510503601290724978610397117752620661366392578491751667042120831662058596772368265214775074311414017862962888317972335661666588106830383522080047364755659273125965326050784521232333028963301506670543331739504530802977052710244619438599010337004075902055354701064750043352771631625749307085287659056792366350025383605209219845599266146000762150846774072480610873460712160773767239259466774724589705155887181035913934697527787011511034330508195071230631732890620385090074502926935982694474742314617672548993868400572794836072319047903396862603749047745086831108344010351162933209280472451667550486074163744433562808025797574970757956197970513455615972949282822909045308500391026951819165785575137833045335831542913390521452096862590623588743885068739462288738180078238509459003108451388058425185325255278598248476414989454687566704499533564136507854998532695962990389727874647216484637087698764777306158332132305419102928547205094913155793009665804374908906520389307567988850097353576412645927683057065557498085896783116630216676543608905484100913981268855259535480872381224280687966654524589486788196061983965952389047482866143199973013424262574693770045613772351089333576494011662267514488334796099936808644724752126541897046371598256737493120102752774683778857138341560162009549654511406687057103116893158263564481271574726397073421884336372686137120040097072635137460823666568186932058798492296803191356632466959505189786642631954048600285832789372824485489452578531568801548629738762161156311764657099700842049225616764476262143797188775599527520598278801236197787705607731407171445772297698106642266137021930291717191339967114644145233422140436059693521880866916423176343086702875902951236458235976888290371909803727020811490234227532303770293614576019326045828612382380020350987316476172885874409236952912015492698831226132644623733247425810179216162391318405176059854613628238748043758887836020685470349056358479560022649944011893428269693159726026171649590500425355279439669913273829719207102094239299086805320200288237003938784907403835166708897329115306160716864431820503783972188493242365222351142503513199679651678948975212389769950071956417214435322251661646712709399159141911131043403032647797177203515710766179441724976436870496812733330477663506905277753941213007122692533193009677271561225037592309131090467954895317443285837665105418380732878002415067494919344421219038234796748631232434635399171932249906459869256353597473893928533841693353637157240987149545909245234433892015860050409613787295137944536956131765138868151118904328301887115393823145000464471963398632564955268281809055052904296638857344056206641957249299023373636603365053861746236863158339158370168168707687528226017155418847783785459357224242229897054291234159521006599354068779933965429560197067874136535813087505363456494427932135964326476092449759220871173202594694778860808899835944628769203020568675451480734396023113191765254340007796688104464466391980752274432992768851265353612594319196117931815259307086848548835468809812705217362146198289234558830376061125752058468738136926348465795381341815844701442623565740026992403133742234993459861383688346279101699494111462651580821635947183539502676098829135302126435018687026528361412751426072402946491780915562708043777143993686538236634997127428300437940966255227314994361532561941848396222248411372816980506661773108461491513347847416828121930301289555801492155394583046899976402494067967562614434663902251093217610738155364952933477871897048506825080019583651518715138986754490886220229097721579204659419355073941199392514798748846528776775918720175837972015617719193558939347075601445238900601621651624111812286575539915211447733566225870032352125279298924370157163673831876693607635642624748026233221520217958110838168756842845395385460057865303892717137908564643381552793688834434031090002694689992388134549318081233893236680563979645734737489759163590109776500938391213947742709333631086125139431901637731762675714723739222377606309827103462296407515128270241569629886599598512694861082608981937303617862482923966088482525690211587245386204102751305180172582816103680260526032826270349498262865058494919415338273350207299014753920021301571858838197582223211016194367803128385332296390094950446213019853116711686073440799435291508524039130458427728944889054819361371606534235526337455365431932981265304438854045299042731775112167720156523637344780956085430538828913434629517436324802809626739381881771878682296119350902868602946318241014087805609543240143822358555790183560048010749622618942659304217153581755599126510422028682261712333575754126858821140426421215899681887549982183898311389868664238722422662642236949651649579689706464936473546944126898264780443788404352352409318426204681223069335705061367828896354942378737381479444062964229899455463164267512970129927623409481050237009501415856372934106683225617300302403106258704317308895220474935327528266213636964747381485803211473489204694259620760327081956720793094170857394447802485025709895888909033129835242683172103512197558174085767823177800860106067830369512953795684197980272076075713048409937344677267670337808901240085047653399688922124169053845146025600955277898469837620224108145920334782121583703428595684765084272130983513164325011967195077207866031368801283019447826784739118801430244989447270933004433164701771567948700016161300856419414030621559088531185523751431230664981078661691803077611008194076077125341704233433851712240837914788743717179020527146124059551136565906406474319598485868518385811228164511717576948106689005285887622173934048509692611121235095341320938998782210423780320768092444484397696636843651458380614585293191100861292373822056603394241008052689114478922863913463896454624706713918535784491165602189241857298714139380930735061070130312948514299617739992595507974462287336930250549092962531858214587498472548455440201320775514767585469280357909100063800946288412064342294415616378571770717754089790831393376468276110407569197195903018674923587730913931655053566446189399064661351567865726625657463780252805416220656213729798141084706012166883816268119429159960098471356919796892010443012750853552711118340980138342541064648137650511832122517201219048328452346476242904260708376045057110453256085099713164270697904442625493532168248003307587048852634882158825393774983014076483122501817473534808862975143889639123177996013200165382852020839354022939404029327055441189358046566393960743140154595136338603190208680113656508357210677329200448583687910315127423181568681929076135424030985740320883554604901415673595162708231078541737532225113047710132504215997529947106507579326964937283399641724907744019014301530178810090480081523461456026759112070760913070274689472350546906516216145177998332312560779525077668776579485090852847998898572294905154375014597451610666969753085548001437099092982092810978029102884851163963901349207528751176206757995408545156884160937638838993505113184381833712215841907692128413653047609775533129500367726332128385185427738919385117482900929228074986980963876865563041057176097397368673187210581100453275176365368360873566754438647191826842260602407596697143547323396662768578657974967974911251657925620552069521093347709739291973209949906567376965443427856352786535750251544991603663532318503788562712723949882471813468772497950526153655557946070499513149254723474006519310694716954753347201963688414483265755924475576053616447778928285598833943425807901188235848945139310663659301568148122369958578288853197352690116264501564582068500712593628760079772116491488443229744217117816610524253393287517298475892249524914493125250176519082761989446210384509801174279841750335286116390518069853286485744384142772379541257645633857545490183812524302202130840409925585337521144314432548225452472424370038107403717234566885315400254012659816210810364125913602135978074438874223196924499841630499915163150709726757707617393132955503264647263327973191914588940560883373907548757248795363475780073206934588596395149402397209269611026438700911043619169251564104077949805045367152829632453494635842410244917189250570829435150900065266386152850494996860352529682221925388734614370449522395170593397769358373516115881776414220699145081783524243906095872276277714122136053930770105356582341073309513331399960016229057786278446741527289083075150233959022134555673942107665377844630393369179637782562766536333562661668849777385108009169081893846357953308022150346554930819562602879738544519589101982347121907375403855257646196026301327776563832036317634474827116268459662642944372126492560809693405215128533542180516869398414657005404853959478784610283012801393299293310865488872758552276793538074504133040242591906704068444956285933591466141684443944995600452747509121161174263925961586725949935622868399359029839107827074905841781076498539527310686370526270681865655693009059223545490805954994590675709430788102755649173896750556906646154418641141547606444645526763134042282137473184008596795323642631033605092316973843824408197641392905701384703345135512132687193112226785931834642722214013816407866456173040116225966931060752528817503177650179914126707589660248124031190071809365166978341644106964243033469769887048575508386784955140432020233924784355446210637197822991107765127612448240362085627822400666946273304328848922276811450605165921389225141233422336099106206377772517192734767594787829240473833686931824589417830653322951907841548597844096062873417630697698774853985065133335227825823113657545334175514611979721076701165138900954236795191146361805163842665077441931079741545570744572037028633851538399950721772672075142872360202094192221397972505165325107785034835706872638848656149026274423036411806608044823555265744646257249206512834386660143020423948785596184806093995850873873705494493818670996970385982557637058170558158538881493960127942681491563288087129868402873995036883178707817721883664109845503482158347470367071504517994951048418251293133173029776520046255207899574198921565314103334231554721980617724793137727610935226936253606136685733143656166643574693542162678622050799264525351317839164439485777138743259069324372629669549621108339529976468516520015224801500355289589137222571896594487380009542375400079756988912528537356678447673465842489263718944244233924704334635762958028181824566762043052765223758806396405486452645302431561032611065873987034847505102238012754129874094467780980298416821752619446329268236516474144175708219881394903032449192195182580559924040685348692431389253803563539925406463174242114362049832246442217588396004494777828071687120120375069596432112854292699567839530296498454348118332634927722830229588839339570655616430436155013228768840316267878485046874747305386736749195380455622328003231809915070107114309555701413184332132608728836736897197314790626631307232994943375724507785356491489246029758514005038238792652337215117716485840289381142058699561982438030467314419644202239189997908931023160640465275058094730867266773583302405941675221662246210217512164481492654454879303375259389632098899214824416521022214849557729662120397204768947825849174850508878396693175010383044792529758481763036202051064359312534435345352058899051522796027156263773866885738023997690186661560052625102451990781835273033110092027070354997644292672163863298533713947403734908010236269050338802683544347298738352839853015472527853175509756805140645374002004613851208846431250141112629207146125675429340000752271125971050066837694436639563488707662607683969584640728112239220363816369021288461452486605865560773665796828227446394865332209130937048504260557876307952096021028996288738329886357038385284310866267895231680835169748191967367697430211656127617821096335172769801667206164891456908590289003494484056995806637066992955415958159314171163404614333429897401069300697476301427883200061940022481255981604527364960339485161222448407205404984477430984370308229323155973833766946345285824028326119032388823828672834441960992688450359314667682688304180295452619332602293365217713170316995944636546105729451022872106428307563566284729979360785706906555551803638271492441673212654042379223576137171408067080659385185151385595560111308256669043786003714798047531117840316835962650303004957436963236811540955510015317858745831233362798345365698586947859145108443351462431860271105279973152935998328835390869279319586484867498745878696431279036950665441117911387727781410600568530535982662469084210177949994322966378363207354585673167124899343903526773338625544983200511244976770388307383072328040834008614593594879621475094721804895175527325306487395120233551874297002725091701883836027953564203996350969289523471530478723626337987799390002975648934727481875154605796434219841815582376368146516683715113454434371648867236779373118693337941628654850340591787823202101444032772313472289252120767646405291275392183173528686090110316840985399248893969988196153180254475271531366684756953920772587167190011395604552046544338286263393538857573354044821445543927635917860659927013384800944180447365723058433882419906249236302952313182353909167176982872083418311771529885230251325580515092060921555981644873863822676838263757003632261125673261277695545269346542445966077696503567442261411971086185999213941477602241480935727231470209141610733274182521339118675637862373733759175308766114140729600379714002845630583515603150771959329869603283913942529544279013356897957221762234098821148504282355089805964782003048351969885424734614427500154894193046266249197593003531850357285915345056364291401377916113256838622836495258604855474926656285454681854633153653373959910297479501710279858035183488962737279895264362254092493666300664095345472695934889102300312673329168321423342568527727061704752377281353028501265624161606861953175557055821494178213187845873229236636907218541143222634270146197932997594234132507923292388410341105176667449689246919739170561473327373066399865092028914990696304817250443891096975109855001492877557426940503540679001657580150482609725948751420511145152987483170045242631966350698725968910983070865767127849830737412322126040484691714575668142479891732368330571001427055020055935578672890353653441848859744270133371725900393144942080089343024461826955088952253238859128013565280185248500986212215825418406523557278662867125959681080100512968984461268327086239506987243788027086395683224165760381088043052056711601945105725168591922884944886144019073865826560830912793704925643553615293114431953986472885073481804813965020095371346303331532592201477387354850253085416761375904098132857967522121676203098996469049739801496078263390836745879271004689435525099903715028998452601013183948508034553199600759309882444671164196763130657909535936175771144599102995643590511374804474762516945803632631257197274070144200862637603117874097530150089307163220298814927262718454417011178475652398089753568392016350930994717130847744636434098765218172478822258643890632342550610086267995749491110453175701532367199945101063381021148963923106118335951826560072843596679721632004611593089462338333577165079958153367932766450502734722198303174401271807015439400406744382083745639705591746344936151896831296091019583485256037431867538371594717212876330684158134093910584621041310378713815524782346452197620015195334163677876071848619823451179941042981754911376903897776139653908335453474583971528250255193492710278561172146942988756848431749819971930973913887524620972345935071530636910426877740260814910924258793755468129755277638735928276998386556296159317870400052160229139012031104324471731041021915655888512550048435796785436406625118110749426034007708027021036992381905504364885911758907154468389571198875828130529830606308533023573496472423128476617996423422316610654644481577962341190249017363168651556610738170467746818135458619408001525482068376132088015325785343256772123534690404220351237231531530765067671565560010115560292866712642312483895820442429846085668751501144936589251454675845282093594456454202959646904534864579458605957260176808723584588723835357746693959887150301347893253867486883127945791206228429988048706863020350549317874658623140726034107289492030166558155624006311383730986218621588921993437478474886755815796686080509313174285144315569652792475213442737485003373238351149521858847350401186378093161688926712136408812096973490559674027832515346906240358167855304729107711526352011721825569644779301251083837024924769212160392384156118203882752393998658999880095788678957507638217014706434024987700407431460897393349479363584540255146273392573607269860736911900454632286557517900696710173244733710564772402765306440649948029653725363769109465580674274391414911620026085347446139236111948242849389448643877363757828377562048979931359521727800886595281018231692448999722297214952625399856644897530636266033328350290902018968554180811909523686117753374165797428999743763089130330827939747127880882459377275126585030770747941824303564232447957707592698881940617362932787238610411182478987403040846212668111178768461057242277170797840272708270691849186118068106963643616994540855697649799272752887233450691312572311275641758118688372521250650184447459793979237592356874310192164257944343904378495164548945990336242430066757649211219031305881888259496747940653297932337678984810923667225694315944912140349846990186754843567576239146937540586092728879986241731500975537734751684288525794567672605823809432403194193862940577524423683008018402991533323768434450233137888002009449942864706932684286093944014041183275647972344406729145236814481048118106659386141446623648058612983874791233807040149306844774894080710816740778226546204329627087313190119775719405647184044352102153494299931197933215183243489010540415779014688492548926944081194796929695467715446575527212623117512230725856218089431209018900450376450180491403790309474636275933708058850046485210562972391758947856772989935773570823073818642843335446899326039733647952949504687354867192829182241845911757377430023502068278402429385974659794520919747917003580602564982375673624209920124359580583763203230193900355923068115528108856713926894446315737551971550515509272256910542419159310515723009481918992564348444814210510465146343124563762477418600542521706685648477494795797224890893381926559219697931120651362602857716645573270256057470179931222903832682118005439916745193160536191001846176574122529801727155901025016841217922169656190317437691475079582400575757297585273175098410095719024631453261673723579239688672337153085616644061409217236837159226821806406990317531511689779819888279486495763096100906152624248400057698760202973420315148817654762003924616740547117269477132989942145741050613012850430555685434598415345777361464410252420389236304481363760199309611042799127947441950132736872124059925645805119254579066442906115828949886290255640494770239825110581945379800128652772427705447651500814019481382020284903497885250616903319389667910155222816267959518210524036403274694574534135962384353104442345923411705799984096019267313833970587138189908156748013850458741015389617937418355154837809766185159125339464879318001691155209542550022669618811916922969889840454122742203823968463358032058244469919329638251335419585670798871206586356382281785383757187086108571832424576880304013529595880557931221618225194438440455453108809509300305041816746713681989292065094862916900937204416848166379322290433498825902987414495564344445638996040064913087930959633758939052386340910314557717344405794785347712603151327179435149107409658908395239671949207116945014217275558872483652954941410560867023734321135477058948014665104202948513260741841568164553750317600841520174275354091427766873073119812931146971816777327261784787546399196144597581168456665175668494504965150245823000050274979320420568105482646108749979842135774736641575641055164775582187360300022345737059680935625713940942871471715155101714677895904826519976150762226699986646316491136674116064067447932118073336015256834651762368029891928647888729423563074401222633948630509128712376858470822344584001341734443385422027532922316931210739862275633582722673708957546302524299670124810298157311113547896431790703584696591154771207839539220097675835591363869036015595908583325236634932671746905030868213041931415874618420312245193399063709435773758516563690906407282404723449888563661688771437874019159971222320389106027480220057859380427899096274862929076587727921980674198842018889625851321345238457148675678844813638901676865572528422351135828376398886256522321836434582354017587677687781228789258031765955344933692496062551695282452461480728388081711548078718170267642629210512979896414454930865847559086855524569367272610106556526218192322803176147940498958224952152753642420667246824641849599722195112181014229644762080430129852948662247473436653640452736379680646438142022861646067106126041945991399115608456383425532157483529756370925916958322319489847118323546161948232784522590485151641698752378252867979161626904602134595815072812855353359254466860194732523848229725175422910689553216185295665216006688437409286651439664942023252816656192258285352976890840618984088603152059678892707310616542288174436495883212918404837716541322622109293823328022940925967434703364679892210881663459147269919549887245614824812272159920115132986626216724285706857039169184753686821191533953919858992912606244930146960063666220303182535126926437459896204433585012656240412982874796185290018797922386009987191507608731102359434438523742958852631244132389014458257570439926898354357297023455383944765878584254008231513415393725876992566643375822931045280067181472086400359467419063950683574771513987700003829829776408535627617476830428960938814385613954598844226605459152173281769347893981974099747424761564525283764817795149236172324470607034501910188990624086972258937483267812565555007110544311776526800837317342012820504872128685549480211620540688470849093264570013432891650134926078901319778297177811038144772920034440600991143200639056204494155533145103384275354119539519008531668610914691528185135561205236240068221246259276261570690243265429901836706422383472932138526846862352240719179540677716165694419647097631446423044625489844565712067349225941905050861334256730647111338373120887064661403743361948458795425010522343087066307752115846799760052415879428819382579366648646654924742046074517891401180632381838757725982920516495794829035068224410196252940010650297748544222372693798802905537259492987551923324433158782772796261622483905101049320161051351867360739283421474651422066607804468396917112202702330950096031028825227484177333221931059397871821406632025749822956164361602573234722047828817211395968986875617502278060327828286081653729711213868206271517054813197729004075530598655185275487474155101615311068905396919663076137425298568843586568569568433211924652868856395124083487130992239429822404450674182852466904890463589797897194181531462772512607825202362429206445574144563789586374093307255204773779443752924800375140981928523318411713963600776445562538527344452941715402506423992707182125252313945311480264634867227680236009916653107869282661837563038215685636595455570684100088557092406834669212984707495893847672154394756845242398146429805064541736447400747913528239751923284731321423871807759270457168214745008882328713606445492615162031995159611015853231025367627658487894561726726731673500254724225628628576642617362170689423274793203028357297992893687970679461275517213250882975012845913794200596259166294947398622591172886273044600825253143225974708777975623510467075214407125905421256990103836124429346701482832847596100706262009287167400026237488722063592102429347045967402755225495826741202676783543964251988952346320064429703358534237254936043730331228060772134806008177514169380836280061645813745104174279406300978462029201099923484554850490150424910443299730110462574081168869971460038276799116773489613323124989265280423779191349349656655166663322231978125109359891732824635041336580587480582426070900675063513566607276866973438868238342509035073764785371737954426020161180343892364180304979749896032850254792675783551524421232529798775900109720514140062830155076261043792346540209542115080973584089090732382705529626791449334787006392257329704710270642902308896704897165828379363884137473997041442118884338324415455914418014453992824917243498874072400691017444493437782434688405293105104102024353396622050959459569586319018711318986171512173915456435267490788048600878769889033899957229635746516129916704924506246426753434054844468295809019388589627676611876158928437353583002534978637940748849142398733669277107890636933841846811882375304995164459788819835570765883750119639710600830375163801254549204827601988425776976674401384520353131949298450391652394019213630188798487013648018097456520055234432212767984232234481337107979455612247916389370598361255121144600597463949700808832185824734822057575329708642861329380983941444464768382636353134078933965084605030451555153046264478271224837739629041540641764895240453183799894680392291834703174365109013573645808494613083608845846374424872357563204696041057511046544081029604851950678519813852742613552080252622426718297524904709319401048684194892723217828389193744279438630083503735019515955420381997708171460727094463363222672823156522382303812128058542235793487080541630556045843728499394180264034532388616781357757267291412038356233675728490905111467755740568758854188954414682163424265740888805592558496215161520115694833951172794540984640603291277626324299463557974888956421922804564523931496765856294465448228667399649207957268169048839838957118871482955094999005350709904192954603535539893696101867992233024374486536503689827901017455938533399373166111674139570332159076655065469843273231051286856796743312428997433580753577839428494457847627792586465725936176583569151042418020459331852745785274644429420731202718551189305546577789296441606690007920768355215870259926494649112589996469650800754416481430254693121270595188503952053075466588468143358210434012164240253824722325082320375075404492922782091629577164909360807206658894727762460275512149077848094741906738579041450136440856812030706455914620341699824190168930972406213446345383166937118575507976651682839873924082330169966748566432124392462497202943066041770236604770890445131904097091127901263388086483196095505187293766649487851436688885738426577151225944624429803161937456053029345185017717813771820614307675255375576043601596934973962542877563218541861261437891262099737971315096484619046117300048695265862919676613680694724939997030432865349625204915779116169074497484282573179449046724208161019985107100113656817707302440792544551594401000059338838005883304929131103197131649036434379146094476588910409538434925570035799577979663945272071399922929670550575632159993439408420986173236316292816828151382959329384252578975119294168254741499426258707793576535447254931346528059432008163358304686795262474411390598080216976477674519101891550561094256370298373361726000243367863039863488319516916775596639455513675220440331595294807902729876005247398029458123064079684418890030333664437620857087250490696767347531788528423591833679935806111051280114406324494487589745890541199672288320157346464831732618506431180605212170739478360880558324292703138109815438492619437833216130760078900279499844875167797881465558836026390592095581238411836359229456863824227164729855651748640545767979857449048839337956241707701768714021439720492139174972328288083163995880886842048792708709392585624574517593969225558313020969451526245153873753254303385407003246150835037197880673216479766437839700351636906024820379301075775897541680346318998379217133761687085027096449907994453928737949393702461756326609506495790680221223433674697876500424113998107125079599962190157622028664455754488154298611155738210623601093229671123795986922624643690839433770639174983557041206087267828423328992399952301746065244665758326285625966716028926706751042645893268271717309461135720903205456290021397486896475533546378604243292576105540192111074327213800769487212273285780737497292986614786023201539591851548112764658473759975964195782172099729930984220977120511924122046240025926790957687729359496040871387892316977677719318827834940916556484090406536004578889811807914309875112916212105055494436844503423596298253924021969659987064191367876100052585825969730424346397037681261760216722837631277802449073168752048773983573090722980710219858196892584339833930801608107191005859197049311496623801920039819976493764836055962453375901417792957133639585868185220203340858200960561702194376231430521254018886777984401562276320914846679986976676949003948187919901995337563702808925249445427862020161413454736837250333094786908792207842009324025935773653368810957145265586881093258927667282786556041214983779050291701014048688696361449622442129583120710859686046198049003061677592867396857175580353880391682454871306449654674601724904807806340902264189189757519604589575912682817954077116071763825007426994473485419891090427930828722424410725670815099546902618019409849779912954882751054376861405184778929591653098125924837587334486387716357496387582998678107259659116625012322804364237712243211738871730527200748023396514495874104219878083777142282472952024577444483435616019683826833739819834205667649290663673248073172015767234982474275332774423930842754947940009682551800694340246806700050291868760567206410908821862194381759965019066757547874745292254951122829139278036127894283216815197910512907478028887203249495373665586864311453504715222369438176133773678774607657650850665936446991740878516391212398345093321007504972539314298470499168765821850127233592937828433849397175543611290627124305033188770858462021101938923541812213484707653707307837267030409867814528461826680121163977111066309643891376960366476374951488231501608637076943671090712341255950229948060216662606600206341080030486980287717480462269165350479956621373574324304571037070803583552952156156361804729959389155640950096320610702222388015714001798559413434399400531987729069175149013202582418531926470307055725309377546073043705660926572374497847233834570077574220804826019480890772292390157505662955769281208339479738492985731787455386358515035348693096344852863038502354930544053879520152136584849934125354994189448706407475085649221631367537536021953038991545562933190933722643125635809582825415821497396679916657714704507107286945920805473874307266071294177497491611786795712628803692597784618461395207537887899055233088915898917817740055223566054666315337560052895414242335649071852158006731626924336823043052071579359085015118007658684520532749185032985333017973257108348347809511022369878753378058519500200679973727085751693733206210741265961073062692681033276066438022300657538240776161920916725269284180784364919233201271797961406815365670452183026851949831024895632652256712275899469870550917507862788008653501048106363552653415483604758459418628766045929763439704846536984490843236111545092763700976444190569328406391568720769234545483742542135209148285636302219922545043857137416083730062177172245716612546520815286809310191445625898524724067813097848506491373720645532282888914542784969423909811620086229008565841479830928839947774940040430431275746371746697947117853607010807238096947841320052041437753237625919741137828513913623306072016987281675629788086757732874709921589537747992479010468677181839796193645160135483126875385456580776086034632369714840773089806096745371939728880659955201650864986838467746002383929026835895638255817806640941138751904088565002855640154565458392323914130877665548060765601418049471292531346011046601418737632120300821278391210416662307417017833839297136754451675748688016029071411700696058001599156640556967834585813298511044904447653642227080767111707128250464912806439099285648571919469050735021019237762179530738300806094247893174447612691315810958579757931742846943482888584510997904016735710330245168898467969067514828164290782012880061507560860150688411705278694880700328220323457028828682623807946542585746467206457197829365502237477137060559619193807276533539427351789407858172064971895048747225496045882288220436749083843481109278145639930657610963355109987375554419096714438439033471097165839780055957825942116985287959225632130653257256419329979051762268634787647514786117945494583428118477660433468072596545770331998227698182788815406584495795695332440562742025975989384919091768677908625297588867492199417382930453819076165151687424140453689637557101993254541798414719432927606004151018654865554198624686289291637091184380562278991460214885744241966811973436899478496395264449064016174917390825768274832593605574239359338208690420518537049995637192446814241336495227950582555539551890294201492514363236038377617402111851642594868123860455500754084546444613807400306925434949226443833618166318476711389841118426314797874300575590386094946019272761757843736276312387050992906322126784548090450911450017308053959897336924284063865215428259606556144629717658891686787249442304913700541497520919796748201852013170520584990765801627351129448514665684816877393834731336255576944281987992782633532212625352659384760109685916173134503758563860471976075193468677361786155061147855621624244463176758308158311399143582977716435710215158248648950457608826668591389490009440491289245332733977645804651146440216727193338913861467015344572839347627703315044430303135578966684740618105606429596513411036614009249461775227226559054737017202178245195651672549736346928234745730617347245132957433219303641444063992881141481499647141723709886428335526533212844367481223739331227705955284791964897561493859619794430621600950256403797800377346267915762238696255633189601116096547319221831318502323882897580355706905463626149337517805972655955511837576737971982602900278290418707637246287852109050295850559710831822637004600128434224441772957503987334020330774314862422085199446727633663855965164593810122084595440669611448886464011607624720488831033394767806663291266431919652661488807644497906180787089069787635797740920086998371785972771753250350667649284813784118184383474932680302495131979263882700148984342416925219870915610618648205482351526661392605602704000545340683999340871315037511217906131407579455540770712203556083023666799224567752832755181792998703544709956716814681772300468795668398675731469861437285960690668250076807285779835299117554345744943836226269921774813859554569236386963698189338550822604671615127464800251087186417561879721542571675892214709766885395722955142716943330285085015301945768178557071516205595851767610815066752828736822128288786538421595583651545376255416893483982256452753722511290183109524226877827689850056446463684842154075270181162370550941150988383683712995827582559493222074307772118456958192856168889305185261068499089972461317429848097025681983074153815885390284774287570300310380207405757351610535566305269206357772540827190350313419555834552645946643985671627087350084684321080416887426015717743233833568465958247901661535964904981068056701897041846144945438569262719155239241430206165477159440963695863495492293821692181558434747753541950844653528892018677908177099539996497455235515060231980619466665881443083708056444177126081738353027432635923090150167650087624396738581858787500108728102608909103095882589312266975153696779162739223128279432921942405114611612854790007735011068406370115571526636363702607176401926582753564383509690318848750282066307416472272767131309503408382599914617610446713916460357537631793387728284183531000095374017390159689528458957394114671583514688912365973081598336189266108893786331803907013976755752742163834183313284555853676905184974531863215845810346270377628235743521504380000074770761168706708606365991977471840574877897685367081047225155179797069825339477263786863948096090764656148220237541799394587116112470592877496661805156449658939676171045033818321418891921670736629059167804428484162727089807834332977562062033186793045623044831984047550444682640090720289669441178027027606528033915013284729771294858173104117672046440835306623458065988377912656415379773966316677492225169477905098629489572163008675692330318903549250713251201381141907811605547758387703457814846162980271816830910858974989659785008119514272538449032070953146814256269595334359236673031393848712206712516022956379136600589842498781668797694182249717433632261774563882424489609218834153842519132048606912185402806574501863481298264329013597490132366160877587177610016114562728265762135519452120395645958649890445358473096210733063081797282045886922228569646222486286143590626

同样查第20万为，时间不到0.6秒，没的说了。