Dans beaucoup d'applications internet, on veut qu'un programme situé sur un serveur distant s'exécute sur les données que lui envoie un utilisateur depuis son navigateur web, et, une fois l'exécution terminée, qu'il renvoie le résultat au navigateur. Entre le navigateur web du client et le serveur web sur lequel l'application est basée, la communication est relativement restreinte : comme elle se base sur divers protocoles, elle ne doit en particulier pas utiliser les caractères spéciaux réservés par ces protocoles. Ainsi, on ne peut par exemple pas envoyer directement des entiers en représentation binaire : à la place, on envoie généralement leur représentation sous forme de chaîne de caractères.
D'autre part, dans les domaines dans lesquels on doit manipuler de manière exacte de très grands entiers (par exemple en cryptographie), il n'est pas non-plus possible d'utiliser la représentation de base des entiers, qui est limitée aux entiers jusqu'à 2^32-1 ou 2^64-1 en général. Typiquement, la multiplication de deux très grands entiers doit être décomposée en opérations sur des entiers plus petits.
Dans cet exercice, on va manipuler des entiers trop grands pour qu'on utilise le type entier de base. Plus précisemment, on va calculer l'image par un polynôme P d'un grand entier n. Les coefficients du polynôme ne pourront valoir que 0 ou 1, ainsi on pourra le décrire par la liste des indices de ses coefficients valant 1 (le polynôme "1+x+x^3" sera donc représenté par la liste "0 1 3", par ordre croissant d'indices). Les indices descriptifs des polynômes seront toujours suffisamment petits pour pouvoir être représenté en mémoire par un entier de base (type int/integer). L'entier x sera donné, comme d'habitude, par la chaîne de caractères de sa représentation (en base 10), mais cette fois, on ne pourra pas directement la convertir en un entier du langage. Pour le polynôme "1+x+x^3", si on donne x=5, il faudra donc rendre 1+5+5^3 = 1+5+125 = 131.
Étant donnés P et x, calculer P(x).
L'entrée se décompose en deux lignes :
La sortie est l'image de x par P (la chaîne de caractère de sa représentation en base 10) suivie d'un retour à la ligne.
Chaque test prendra maximum 10 secondes. BIEN TROP GROS, FAIRE ATTENTION
entrée :
0 1 3 5
sortie :
131
entrée :
2048 1234
sortie :
10314473393184679736869298135856868318837274800666285917699525506489711515683426144545388948855924836610603373058799281849682651065988858782417538649301179102873828149409699413583084797951635780398778447732215611870761221393264523486002711233415134476171948872576575778768058011869312394591433671496879353256738653311677337099147038801178802825724209634362823173593923386084549067434085830227178209239457137723321770731042777558081406940147139667990254228174094508419077175917973307871411709893603768521725352746054623497685665327201622303372424658312521419745237362576122972550411123177530637072736945420602737409247085086197444880905363205329115498242538864156716516004470724097605836056043034133474693083990402162129452692576896540277875176000967208481663008305270779098122334262775595417270282185179548580515206247779118774906786183050811702471674146166149803311182972416699829540706588938052114725525166333700534024163518525835705844865095812434193830300810584567348339063060254784935172886897905368793945036837060678840784377623212307066293478248259199295086890845629779939516438001812731583068743144024869568176657542850823599628676354743022896101288541512338254692855856491413860404584618384121873303041378456656136366688754986770014955682983791917100352816811205498775881167027933860193337903855936566654695289705441485007450284401317541731400163085203202464038923977133729728444995448705501059566776050331467672460234435651696388567462253236613657556602492244386233370516692785049936212947187784092471105265363251362482079054595394088226079396643428440406046715199288972892667246824803025777050765153050158207185599316188815127235269005260845180224938784405752344000196617139022210902941870017230276852467661686273842434092129772043778649314239341843067737377741465354324338647802050252602973668592651879269931432960377904833702477294624579415798930596149523156395532402286585254141623180332293099332498635969118752013374800761843730343195851520798792002080860894194327163823932070017035680389655943108043707866824600318114763717790263778165435145708022450049443792979191757650574366528343895054081735118627208952467449626867677088042416506202076189774198997817001248570852909547095338289285053111855941099875518334686280494716391040289318425253683527142114431604340907441422236144080530900382772341689844103805677753237058580274967498853385372790838312705823615800044575538898621019951035085917874388422204024549141803950182994201831369099198598374090124626190118774284700729042114162959165413089474734086716292643850700400406340750242321507070619133318635396559323917849164333871996535653848937867702658108518399835143962001793078739201468119223976682639904731309585203997453784169831700998500778160634548765947944279233550582146181695398959909547691025726626714869810471970739115983438642038653385682415429105002688522228682162612436744486672814171552673109044377400019892612275501152777559320067108877299876750768168850326730019461670989804870020003038373990122722474508992394073677540034473391984833231719453945877501937042759481310393639709816188872244716857492268872833102982078465185312761755684203508245448381208254842095952815314087257537969774766056295247186230697371093839657730397637544168916216667810424012567555201394649859106251176301599020289407279821492798749147519888069572684645064480836781516428385507845669975519975928489762754862433196224664092561466669521053210690184290115694686304047801672007360745755877798083249471032074746678326760777562068626758786493378833570594813354252422299847280214393072425539284457992444120956088926825957873599834114497506875465883343025578867270384714629507071003402235125237529565373523748077686265959552494089768426060841494656217411034481744540626532778538657549667741238261506418371053174722635526773785021242881966704737392966299648978271769088516861654329702110065028816504471781072975236177697523951007574938727526167449673078498542887784823420920429805679539466082273691543424418003263211038827449886176331612488529432418434425860530983204299829202356188117426290864691607420159544384126315415139135630807561871844397821347400152622804240755340011269696423287025285485292302088384934357237755035699366638189625531181125193383389723830647589472946191712555406867309285705445919620272097183713726168843715724243016765761155374715660926057575081049634530830629730713712369345989962781901018514331036536005677436835769699128278780798200465397519276260301561350997605373628722268778968548647449512690233131798443444670247513654881929426065588883967298299917741178950187580286494695210552534928465990408111784875163326728834788138910877454901213548058873028414733338836488347773054613049041996658206599513569782525681110439198286359249052633610681951120409379259552719022828783447832344212431741938521003295548117641298227626053960971955731910566050122072558679844314861994830797095997963457493340055158622397686339415683180777837165777972979030831959494656326547055633289670832464154676341601098017831805971347507171832566100868147771903203153822356281849151063886504039586410790226177118926760505755407745662375562229586789005412980292840056240442114594228302958524544907980087806122217153561319258812689978452799943936238249700636956924629330514134067997760016840369573412828754248257152755089643902983024183219409057507281331813285253940605396591570925809308570548614747916596593749607785201389863663178476019837598752677260389592214179469652664007023942906368778091550213326319084705051572819227409649805948085343238382671203070735697339901504023351537723607367929202708516791075582458602933717669812894991344482493558126921433251572938017046558949699430171906672206090545199250643433984479875587439114566223311894793120858376188058387387345804749599538648445521143907871771924818398534217242865162634534433482118101115501403774591344811230907328917289612821722754807316022352442306096443193438012383354958869370021264693159012494646608307899130024017503563146335546183133255155920937413840986232020496425459013547901019263839508435740106969164217538914132168380990210632594780684672556432827481460885342128564983920575848146191345922629358878839154220237358501160366713657892625911733131435878086377970749321346703536617481524435402018093527925555433412750776286251811363515399174677633324800254403961657639211254223928651452505341767410406901468312052432896
entrée :
996 997 998 999 1000 142857
sortie :
7971292236047049006546482329597401402330895786512028195474027982099559718786827319212711408464179148722044480723710279820963196954725088318653942610492387945280381058067124038054064574556883969432540983638757902105511454251903073479371988944140677221269685742204564567441976228684890707288708667628792220581564994811888535294788773458599423679606560472201605872239173034978022721054875769256062544358134196577286565669725479588868122157333164698608173243526073131420763236286652870615258541601906887053522578440272973802578636015863023956948586443872157998178366119806625807702029517975757629677367914882697463813264796960672983215001827856237781938478823190048989639012865680757144764985790174169291264035687547913318458789647742020171123146871610991495148227715868472064169760051388542410741881911334738321800186613675030711880737762606801516917679702294600805940364855144403364010168179248740217218366096593042350160841408286686884483336621407889442831901419277510717793166011339703239877782123816101206558170685056237840641798627442745694436269945951351620275481365175900041266193766187547281134200456452867063298952238409911765935672993640574478237242220473094234301608889962857939208569824691471462014836179493657806509800804531847260422947274283764111886860967278756157607532564333618234564724031497414211147367385990357771343178944094725455302047882702490654022643714862778479732009076369495359529015945992383877027072823199943609671416742277833642905857926255234155235532804206105902037023313934321820241753527490422903997974230081074391951001735100881210674442077951620988485498360656051711078561238312125343444710128298180376712356706869585362955870014910858388907854011903923477361154070575877300611155951595769184726546874608011772904552756405876092390227454767957969175247933855234481699255434375100844517202964176414612750126014312129518720297572461310048498690239318772172548326987570570229267673515357293080347259717989591898952399390948310393587270999159844342224970581206121383565139642389240402366695683355884646348490780057044444019431831013737203763404533639276916211836088181844316437562288771663645444334512298790250532476094960464455757715324001774402642609211838287689587481941140974436715623475952461621774075714382670776617779181236368010570325157059060133217120444548097720158486487148208186742855396663089362879707807398761402224812457676946976468525655609018392798895704099622230348927633691025348641856066171656953466120239813985569593936145769670100656368100620332002966223081542166489821220185090430546156139222785792287121675347724098306488965263248576893409749041880903732720391401359469044938414711559715305369660487865190213964222165070479732651293278954652703053119299427966512362471154579239835201327572983461340136956619692544664042249659928946137172509866278506586869400830794542980037896521776746427898839642394981321681376495688385996883213430262993865147952513189629712323429845558387820191418257668071494719950668864792061812119670030903987363676538907018627616453029996308531131390911797037207282048678797802487777272368980020984300462574620287910703054143857046712936586555203135073350127726314768974617858752470734768755506697908863962457115830323347923683324285065007802379289012147435607957568851085098922046268999961838618161645477950496576254058088489556014373379719320273824011842295848538944162381787691671601038471612280317601848441439012149325687467145008490231910052901358452824107225212782417777615569137443992766171216943297594205033114433260700932280271811170146417216331581868228658510302279131244256498580874027022655541804007281114263136842348177346031850027584932742299710010674561200744227980727730905985540683864363130240315044927453907514798578186419287696552940571645627486993548585706746691346267743014542909898142446095241985257511971908909577072094303825252844754913112460812449665838318339096682618703600459818385686376611053391269528339938458137070634485700598134985955390977763771744673090323207580653234395386609444286190419833449922815185970668412067342027126057960934533402224877979323256117207296987185902546361474737987389762043278321622680077273817437733283164070694598081842476748165170446201994070804403223446495074723190015201314765626477528003437939513417471279495694334953084870483079854876715294855246644325784473392668020063712425896801309468009151764651972078127118108073377686254358726058149127666272741302296327483013662684946898374712399582042777973232426004715737740823929677302955949090652741677848117976082009759411297057056552964327242885256616294988349670110567059271213290568363018628429819567007162792839644450037024235751322000630825960328310012515375732754304281797974895058829976814313811343934001041905936618953685371652495556830126032288762689021008198795634867624435727999431652895623782863231940936983871302179040085526685214390466717775942704857630653685591006082535388373003403994010822572590673687659647530018547423089467784339441685200711584788951748337154402533979952819876777170095699535710480259301011312452631046509494876509941710995079510388023099938377439917787733257082904932029016368022559833328904565304884293978663340917359247125402101
Squelettes de codes :
[GROUPFULL:skeleton]