fork download
copy 
  1. #! /usr/bin/env python
  2. # C++ Fibonacci challenge
  3. # 10.02.2012 cmiN
  4. # exponentiere a matricei Q fibonacci
  5. # in timp logaritmic folosind numere mari
  6.  
  7.  
  8. from decimal import getcontext, Decimal as D
  9.  
  10.  
  11. class CFib:
  12.     """
  13.     Clasa pentru a calcula CMMDCul a 2 numere din seria Fibonacci.
  14.     Se stie ca cmmdc(fib(a), fib(b)) e acelasi lucru cu fib(cmmdc(a, b))
  15.     unde fib(x) este al x-lea numar din serie. Acesta poate fi calculat
  16.     foarte rapid cu ridicarea unei matrice 2x2 specifice folosind
  17.     ridicare la putere in logN.
  18.     Totusi avem nevoie si de numere mari (decimal) ;].
  19.     """
  20.  
  21.     def __init__(self, a, b):
  22.         # setam precizia in zecimale
  23.         getcontext().prec = 7000 # nici al 30k-lea nu depaseste
  24.         self.a = a
  25.         self.b = b
  26.         self.qmat = ((1, 1),
  27.                      (1, 0))
  28.         self.res = ((D(1), D(0)), # I2
  29.                     (D(0), D(1)))
  30.  
  31.     def cmmdc(self, a, b):
  32.         """ Euclid cu impartiri. """
  33.         while b != 0:
  34.             t = a
  35.             a = b
  36.             b = t % b
  37.         return a
  38.  
  39.     def multiply(self, op=False):
  40.         if op: # op e True cand inmultim noua matrice Q cu rezultatul
  41.             mat = self.res # doar o referinta / un sinonim catre un obiect
  42.         else: # si False cand ridicam la patrat si retinem matricea Q
  43.             mat = self.qmat
  44.         # prea lenes sa bag 3 foruri
  45.         e1 = mat[0][0] * self.qmat[0][0] + mat[0][1] * self.qmat[1][0]
  46.         e2 = mat[0][0] * self.qmat[0][1] + mat[0][1] * self.qmat[1][1]
  47.         e3 = mat[1][0] * self.qmat[0][0] + mat[1][1] * self.qmat[1][0]
  48.         e4 = mat[1][0] * self.qmat[0][1] + mat[1][1] * self.qmat[1][1]
  49.         # modificam rezultatul cu noile valori
  50.         mat = ((e1, e2),
  51.                (e3, e4))
  52.         if op:
  53.             self.res = mat
  54.         else:
  55.             self.qmat = mat
  56.  
  57.     def process(self):
  58.         """ Functia principala. """
  59.         nr = self.cmmdc(self.a, self.b)
  60.         #print nr # debug
  61.         # acum ridicam pe res la nr
  62.         while nr > 0:
  63.             if nr % 2: # putere impara
  64.                 self.multiply(True) # inmultim cu rezultatul
  65.             self.multiply() # multiplicam qmat
  66.             nr /= 2
  67.  
  68.     def get(self):
  69.         return str(self.res[0][1]) # (Q^n)[0][1] == F(n)
  70.  
  71.  
  72. def main():
  73.     (a, b) = raw_input("Introdu 2 numere: ").split()
  74.     obj = CFib(int(a), int(b))
  75.     obj.process()
  76.     print "\nOutput:", obj.get()
  77.  
  78.  
  79. if __name__ == "__main__":
  80.     main()
  81.  
Success #stdin #stdout 0.85s 7284KB
comments (?)
stdin
copy 
30000 30000
stdout
copy 
Introdu 2 numere: 
Output: 190424356734624387485009768471757502894402291602333519273391184052044801863340156450551433982614963137464626804144068885630838500556036577403106197181989289479297141433926114690246564834493082628835531989332440953142111541549920917976020744635281408398688209952783539056482888371523133730274288541852404137830277112866337579693720409087652107913013085800297115487624490823010059245505107399217576190465207585654967892214794886667550037433102336577854685811722905941067193238224884269394952826248638798048234335803688651014213948200751529795496837923745773937393225342531979064080528356666322945947462315826624714006444135626792549585770249106660715795233034514509461462571047476804947095353038731709413604410706082989735571615761791544525979791564231042162639574649793913847950777768022209032805074411739963820433355637183397460799929108660649155753351040248072457511184392614659387374354009064529212219501820808022224254959797983601555439255069670151995180872853245933831067681253893045200748122909177621618865888274982806108108224652705835631654618703320067668928532890641087168310033731402794698735157919378188133117306315981822841850882715676881459373523010452359757757730209430432193850558609774837584057102906893248272322647117645350723205244607943101821181235968602368736523115058668053371939887711901192490071469480182692668908396707634284398037976199972774950371867093141630250025179315701897463715355833381673110697144421175942492053350710561560219468751250798525270256923881492157388526784143110541346731890547564173293438356270080974640907771615944252314476282445381552354798234842808282112001233648009210548599128260379934163713312193208028778706216522742740555896102830298548031740835447247185378992412360954041922790202724474186846793702274025286479940250746228989799760200501884172400228416272067282683327140319184259264567359928853332310617107287488263439326591202485986243280919771118019129447664771514479467005605463310729390893001119407263077036144375706590024849036879329868026084712649637876873465378679900761787541029475703116034691556396562517413773705279395762047610627787872041476180921172984503307343624247275269298669905791091608330882831729028794049245520533416768710205644289656251977864757141787227909245022543090360998461125360545914720323286101975646120827217807449905283159660498495737216937925224220925817959646865654341315419861401742940297128699298628549773684247168778400114516719135300030465459498197355414069746442405484242231685101290717946738543535232619783031259290155129893655271487991702577847512813368752238721137750254383500690621952746226033968997813655493488645714975514788781189046117024617504325310882043767959380975673177274926359358292583654087983221920870077293934239875827463518298300942513479387350032283409586344276466908401612103761669386292569985263915582316337667226479966822531017127262124126242350220520835808782073624952856090753701759509362092032963961331581008568304021317953766850347395116832689445760107136540814214021392404331241763385641167816727186602042434105781074483509223829114227763925966048436133632490969766152896055605048885766796378949073212628193430640740722928528100087350301663849955836083115750038383639292896952773844600095242336452075010729083392972075428177061684951048637714304066297658482543321955286005976030968204370095181702023363402031555321652538677931433797795401396861562539451022181528705363045189154505059528166314746755476011502487747441326009682051775694205211854088167708379369293978758459025563989045517647986934579669972224114107933225786692466049301817169379971620339839705156808894916340154157067206340177881597910394919836923122883469956566283272814177296166201508576234985105669894997329655018310680772846362425663316486101542675221749699569756256414329609774304473863523018058643347466267279990063474997818081994546317355545376345017663336649755874465027863368151754962824865790006195662871485300310860288324611834283267430677264487885244717947323119237199196575647336666357369141659555194142778108151847393235436240183532300639063155468238991712663011603170576591595571472664751062871528963747411528273406047499766374450194365508838171233663717001518338235490852659746921711080155345457927795998493532623893994956972009135169184397320002286945702914321715935739878525208208926296431939949307171349220082594079093553686881433959608920728155807806445035918273722100029648066756039578772515917074527634886032362827338065671597516767911566209444110736807723932393404714106562911761174190456599929671153552179790485011049416098007721734896839029450954557040990787648344612444964092277139936667125920738271902097280442646213007400968800247071757369239144614535293019108236469601396923710806931557364306146641996071933792057608797017958975870495071669538215660519182352267182748664955758923371252361232661690778196233292135432281281858129802490984637885390804066881313464757088720129643942223705209407348890279806411293021285650246143136205562597658500036439996546162852139696666619638978247206779718435967985886095207170416209049674095505101089710995116035722625784281756648089404646506307276336983902192498380778218707838355103668676663461089084712628173914937789814682329298963003642066141999438040852852926088411154831459916879782478335187037234813360178749565388366838026197749656764142432095580920896695578491964252987317907494476456394780643926219675584551971130668497373771104297328252823720093716844106963944194302994447147982855630995491840181531036229308675675065396576250219949429658523027680054153789230319144564667429507895449704352702106699199775945380718822402982347784833335802479031399900713096525397292042172338790454227446834531599850745011939275745068233867551394685972855095171036582140355723560536009040573497122931318666092407244907750182876961042338799663939805503533637073908215976861289581036287788014438378143797673135789533379021182720664243998022495426262498385471169771002394605640491051778090803632911801452749770546566201976833843783851372376164467387704539821085375293220018508867444967714951415100256569191282869896229350884942425184141898975551306147830326257128149637401473862981964515934107227978070596801874656899801671675793185108559480939632054408671933601514519496788580844086469519287684603973247694790730821810443367097960000
https://ideone.com/LtfxY
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!