7000怎么算！使用C++？

Question

我正在尝试计算 cpp 中非常大的数字阶乘。但我遇到了几个问题：

1. cpp中最大的数字是：unsigned long long。18,446,744,073,709,551,615 这对于我的任务来说相当小。
2. 我像这样使用数组，但出现运行时错误。
3. 然后我使用了这个想法，我在本地系统上得到了结果，但在将其上传到自动评分器上时出现了编译错误。

你还有其他想法吗？除了7000，我几乎什么都试过了！非常非常大！

Answer 1

1. 您需要与结果大小匹配的固定或任意位宽无符号整数

   因此，使用一些库或自己实现它（作为无符号整数数组）这可能会有所帮助：

   • C++ 中的 32 位 ALU

   所需的位数可以这样获得：

   int i,n=7000;
   double bits=0;
   for (i=1;i<=n;i++) bits+=log(double(i));
   bits/=log(2.0);
   

   因为乘法结果的位宽是所有操作数的位之和...结果是：

   expected bits = 79320.8214956583
   

   因此，请使用比这更大的整数位宽，但要注意位越多，计算速度就越慢......

2. 您需要使用任何快速阶乘算法

   其中有不少是我的：

   • 快速阶乘

   否则你会计算很长时间。如果您想使用它，请不要忘记将 7000 以内的所有素数添加到该列表中或在运行时使用SoE计算它们...

   另一种选择是并行（就像使用 CUDA / GPU），但是我担心所有快速算法都无法并行，因此只有当您有很多核心和较小的 n 时，它才会有好处！...

3. 使用快速乘法

   至少Karatsuba，但是当你达到阈值之后，基于NTT的乘法对于这个看到要好得多（两者都包含在那里）：

   • 快速平方

将所有结果放在一起：

time needed: 13341.269 ms
fast_fact(7000) = 884200795696311224786499369689772651514666806388814861406385961717517575472515864954798207036673559256463577910069306445417817096116575216776553181713921375210379465153938439049263616883853484643729844940674475647650870604344824269642159916164958273013791974417396005874550315648423675068110055177904991484888565014263738006300545825802902818118652997982634521790487546878590431633226511238793863967225422353357319332721094496553902561094503439568089910390747720899610159304586511444419676713223574275458238100352647760845119079673155580336214260228575697993754524390945723587404211018788378527333788204858075264094396590404513285130492022617379667915399266648038723695919100166817564798269052881196938756129115151448471689737986356043048876202446920801652057684415380094654744354798844432367392997997642568177854800031846540473331139845669265588398801815321514148385733973889061856325073738585560998548185884443184943064004498731436020660285218256339647343134194932640699078804201414652898682961168002092777055164506393723639387552376388298069815583487788557046483488721440352761380660387403503584237881156754397843618241608125541317125495569998315591925389260654582209451436966780608885468296586484692901509055917101206642066380907927979297253227139876923101729040098236148430865081332196280645834104442228137861087946920123498276952532294230010306359200738566247039986987388932202758817576743684575311132635133137577182489260271367015843055041005772657904632997010284372234563940716858397556775200720550613111076111086135629429267480860057242698188201578899440146126065912167156862215286809027141581633856309488257921141676385697377559262990879462845705251771041712026748169621704890211811512560588248863388597046076534881987211558450746858724123569436447435159239623330583329363208324862864476140543011155875862403595858209667082106226820153694025187572243191086621753050924952209038462990905901972780854997864921179683403749915527734514038395873323657913026405816902464407607818773546088817908973689817740609644878448761609733393080219703179025116236140928328424060100029512076899519292058012015220025919924667705947962128251131331684318173505669118392027311761131711280198006195129438567518129233141868134522729596421891203230420712345725338114204475276479160774761422193727498612085560018451766831282249043507608169129586355221529351357230150385226329485889212729477129482272941174869667519443685798247077725569424305147790124480550083005313701400816440018234414359634858422759615205221157446251951553540327071423865241620850965806143500270629877049461976781497882136656900219628820837890869325795628009247241118996211427822193602398960178877693899755708030463426041643474998949435529505887863566376905850160026031736704766515959498750313382385056049221685874891926295316999831444459037920950153539469269065843287143786194263364563863713809138184871751575050544442348834511348108488697444589817889019597581612624691561849852807932084855842140182146985662042621734320043283104079260435216435648471531066210894747169669255790918482389749827656911356994975503462935209258227946653084015201926234674910727340621274870809356896858604555382709190090086188726384203788494542001437157724591712957037802123283004648790387404475331085521982824562808511387332127545527247043358838373539484663638360460047385006921583786929390598256429586384681277918690046827516936775037189552352022660029061300345899343914201217462804462461129031201325891728392702165043836920831026641179605350262477589107206301865704662486913289332044621856897265791099826877677439573792619828485751141859811202065569509641147289138950027480042242984726705050739438612194496229741288679609506222780687943170593900907586326405738199366395311410155736091495887001627902968819665677383786063279455620012663729837910960240479881844257584797349250633188214560310758210641369543753988083619301480025337982273801479491569982113024962814928143663856555190869712634450701927982376591249169762149730217241788093421498752871574345065979377880460049740058489329384466377832988008762538357391603587315730233973823425708191179470986067794701312221468274933340320197688969367808459315506018750238841859435941488597348033133553460617520819798501946602234675551675045836873982314892195840471126630563552445767128217824572422899810041922843352122971651561354403887378244763376133063715692367996086960857393692765968250771882577033394703412637192251694415225236208387586860092438676459771831818209048010229071311967554555164346853324875531999045170182005851932675503263765640691455597084838683995687354728670583918903981412596462748283092934065130931455166025829876379171481159856212790742229145219584104499779676998350256632843866182461342863507746245871166845870902567130328393471506142425809921854265411236950909977236626987936917638028408232482018295525568866984577904307233833953699800366081896471903788517117723892980035364966242071313021191620914248928545345110560198010087286111379955002210398427376099924105290577494616474548750828512653818026158726812183461162242501338619517469969307373762964389574480736532908025901060157596932632990321073314445603216620493213820942703264762964912361992115762596938237161797449045944843616336203069868724768120694536711693716916729635843781759752770043235393756154611302465543588959788720426193744365630707206323630788979660021304751828919540588944691231844546997384702446985800537196534572819676839430655715036449664005928807275389929836639753207926392187614755181682049410507779299568545850647057127761022230098340990966719763205962771391462254064722186048190646353238503084724191873475293604865074517284174946007262036020475762927058958111011997007434564174959365537697237570215440247037554337127488209512340102037291166004562184175320392056897130638496346068279514138745265713492525331536371457275238795551062143918352533804797218147668329547744757614101173242368101039022991996265336451154979860903275248450518656391639116116785830652167451076804522288236296146934462578832007237647867886213215045051528186008727444541151961864777705091885699227073977559829452937561266113668045618761189152266475538155304416881737675271471942609316275606157245804183629404965459159241292594567709592037738791080059291796261513558989214340609719486288863861222622160721279564969172790144392106239879849165158236377133786662821415060954747690529203276618052700621021856210772670565529452276916669340540978444780784198038052064745513077384398932991789640498208682279499303540329016861562958144421776967955604510987311737625286725507320591946223469600766390629896220932995980541393443714069748042509964076360801791554036805320123769481980410242094695480639158277560286159194489257594640603936458778944510878787313553337510041710879300763642464604558190679235274820278784063692161689262465663664448743540740829439842003927130003522412205247053816765536765143639760677881620905994650344808065845606142169201248917433121057223435712653979275064587863451689936930473327632757797932454037812981192351891512939799373478629666763425387112518048359797191093203089713135355004566998836940597221272549797342488827560368761157790607470490269972435332115531312345609087028775692485708103103712691470555628084137950044064576281858329308521673620425946798965417275062193373950479763518346584990456586033501040948385049846110022464828771110962534606724143928658624693111264033230427955230498085958542745924751335691294025353089014040184549943991371128968743814381940660730554536073165632899400773191770646893406901671510291587883838888734390516466271782517818562388743480934545664726631347836773615263786256995929738357246207121361320682076711869506017451601932983743183739608500880749703185463869614740005667933604331331453117359311127222046582417748009045490589272928563300919678525666007815629515873014776580459649431045481591108638336673079911807905667040672051782838086056550199681698580980925988261867125586450117937533973501715852857989649946439583689949631047987981179224994962017309113822885471763757343974959758990556131641869536938856411212823575982313560362642343502893077126676906309808719919795334253082810758042511391178464276866234398242834749638430861547602728968997516156136834145157697099898011848666635607425847974794943652030680873434012001264440453540632679322183913136383758932882243778644095400091591691382675814220349114956820594175868773278682006321550632166380325927140742097927041472664015985045840122383263787782872857558584707897431915368114657945073091408658315467508344106455853751224311398688249455116731537871058913336211080766726179785922731492443558476164352307700820198189603659117149115747276895809239319744584069340084590743251255133697555422357016427363704321203496985278881298953952667606211767184931690516850466129051504235688986889574668693027006925402068792939285389240625155360087106411789036196276753277873015795253442843297860670369837300464747479502452661953056495860467943165792277224012082572107408934229840379964071370940387502083410383231247038708878408434586317127664196271906334484661025239635157833150810638117123501141944549105245353840598400392404430858111186659187140831007113291319985177166225148608172043521704469670558281361535136023580884466882921308088666366578352670603927928363086010384240595489046732493380895006559014617823474314856058082805766167625422965044895551042155265323282063457811198880572069167504149723789623002454447671022531596718119964709440524694884215635003390852157950977046196242171302251747116855365058362702110199707331209488020884238823462234439586137918628460775858086831421901457077502412700682733381362130866352493259747205012042606444920323806513189905058556890661165047467244905822175767435643136539374076426050535462618940163973543343825804280613987814956441674330377445955347896382964515325185989383218156427777856157602490977152930309293749200522873745890462270204790522572574592475926517379106396586053390545528452856194924254620982631441574376725455326466168621107550877412154845358996957274919776605857660963184627939580413117546894887180082659906132006924009416958374801487266070243590182005190240623062801305973095674443425194951061680602554881817271972965993027621768416461452601687574112740434876596368916383062049470921602238045348560016040552449064240263202541048474713723538673265223275223617760917413888526177116291204671310801830570944767846175443067335885366580332237074901899672564635554503315649437974047496086642327591054576466079087901161700717561120378521322282055226164833799865344729673606510995334776986589799886665374545794815902642309844682045119800960735077540859914591408963019417572675219773612651910605973503031087542935257838147286236329586025803601903361026727955929183155614956110033506831759035769722047690789790638115885581108224320978500255542317680572434053897430562889863993804506218081508313996341415673285675721902654098610873085597900992290520626318990720941232912565064805309008084577492490612870872296726773920711211505642953078742266824152018125213045896019833973105198990638991004426538072226189241749330702395337764374338000935313178072609611594107338480373633575967314018355885344082844670090614509538971567851825703787892342833345437449373902235502002167731607456889946211891546200728801027593919150791374561573738555452338954627652802633701231480704377552623163476616985722964951569395680888358767032383411379088496082480769492319808267810827862585367890824726224336742960950327259979003037463879924888927820334569767437308562908558267096924711529333724116062273664200658679804021817767063908874776235140287867129675936041047323311504381125352819835242741188742739856932718842001368875780227609408144839687801829857782612272323548950763626892951213927514735112173961664360638180826059980828359260582424897021057392551031712019440220819172539801697392303654536203284456644627655022051833428223825293900006285776065172251703775526045321767850773130334806438019535535118992660455112037420851525848164474625486592182839449765283020845640197204958549719589043650138279684121060382337049505317843359239371363171262560781239868578847152267486907751271834233034943391447144370061036549401060548505602276970056247184248118042579362684455901271851498143651967030118955724620098783228470485545788703873028797848559041598982029593500108247069130146241228605751036742985711202123210798304258566028240300247100403992739624777062731050236892883483910812710012759146653637047561480118439220006009572756527079082980201279259045960612146970038278687758850465304042712444426918837208678593204360190383325670084059196750632698410265783054288332324179491589094901703305353829370449742442320660381372795612172928730374714898383291514613909003285422997467349965140699192399284318453255180133892761632267990507100732099248034543199250902326928802893732728833681060610457172406284702036368591149118648561992722641430462905849072322190973024694711936660505087205990802922943465250037719316292156945146850904351981122683924093898960583110018307127974460602468757255041576694551065420639322719341482488887085869590946509266808855087401550627879183801736871396403992121504033015203373769219758001579269201568315182935407399447233253130686906242106786974664208537547934429995879238723675304866367534481956734001756288906478978260323018673438172704096323937123598574366579571460129832228688996842031331892936328243648717411659356638254528415917609623185703264482370115682718828629382000058888692851538899573148742088539377705632726001590024644070985985010178231193799653504962685897866632674758020501473223503587602621821123265831694468311239921779962493886667842555188965897023646350207755492317928079589700359457527007142353171414823835697130277760513305227055468247140382194643378213338923517465403875762313989059174110621232913438255361331701676072487852583664321195419982420292582898015381991161949235132691390901223065436700986282576381827239557603694003796686144598483334991059960120613920559989770392673869182425574416153131251992575391650475614665711794965382127735837038501778232524283787912582787962001827662596612798456508470589797470490916368349582949171755552880438801553802063544529473309254171554071224336757978244256870123371455830419083892416975274615151251401750369126832652603109696876142758105163610723621843536617590119148666657208632344217566114717774414555786968614769297098442343132101284266656485680339740830243251759476775648179376784687978363225308036011252776156594030182495542102819782460397160648380830385218762729991903641417009473683866645813809311217864780377048354340272055572467208561533031825212103730298900638329313997470386961678067710895050320673731192523957283763498296303186260792037094675305565582304722805157956192593419503537595947172933821100676440426045474488237259518397952115039586978098817690363344794437242041563431617639273253568467753058730864022731915418138490527798174335395792708975983228634593746436637181607292241030758099456904812986091406455914560623848659340130806550409523133717388598566710923272255609666006752325870286730677120866807241473614332209631187301831475314321171963620702758755311304568421601360305710342549575171763157653378985381871784892825692631447619331145025780268587796861678044665705731163091275654254300012815692229998883687164608914272277038179449761579972115481613033518100521266687096082350206265703355080713197179841417109338071427865843012645036360244360185280033903017306132872850881535531191781484830652739061676392135971446920668886375577900065241693549334213925326571196523477305500680665126537638738308090070765725020150387347633253362699206793180167504095561995791867086091956675495932428330748871559766183731548571322622763479665294121079051909692723236746463669573946655865309143947040361897831824524501403283237257577987472144030499362484595774268957509118680128580610380407854786956352558149049742982723757206848926681332324487359365414603470843671615850936752194142076945189945371887139664125340519172881059114406094020816359079700647244818336183064217453469635453623900467299176450206529433188532099902615087955525907266900204962671257609110148039268888949703455958462017065439627578888580593727677341225086930693612059466921068996115807588265988998793474645113278881228317564786823656252981863946547299007048938249114973548613173559458434855136885754303229233640454687779361012089069089659825305503372133772383381078350172972910110307365613526857400957924064499689718168184627682319641267270413487099054515236209511840885476703151917998660274476653072297135863178542369530791924215332760269744512879647263132922220554094045982583236318036844612821086340302496229893284696342480749111814978232458108837416210591240999841400588581875378703071025883417204465264286837323571829761851700936827190230591797526996408659952448206341975202237855299686148810153448962278898723453234616022054687176858073917228040951497953064352284645916246363165113353427629986375549330116588255291992668800150049248013836093164816311221781609921510990020456056579835582509525087013487671892086707028140408142552478364111789821025277210439620323921683112617227729747348702639373800753836828798281002033418563708616817586965439772941922618622709746032217599722752537987368418224158883151410040517163245172496453435716348535213287268431016538324023904932610127365701081092273027248636688323882655289188441235224385917758354119006650197827341977475040990126596701858800795855307671163226198161462524720118657045344929010427098289430659588608883002040612201818643688868214667837664845584715060751290024412411315770708978000480581229239630748005296160467526053155888431161210136968533801693299877300545528574023542752435264964608516890896461807511172971464718536719909368638172485591812373758280067801628313910561144126430991449035445497904251479996550959026445819905743466438488451497333872194822842437998397397293279812339918712622198446321480524186178254599072535567811602450427447840457700962243888223402032036413674964097938823535786169147223198971568703492148127944105486540963148916504126072114170270398640818758212735814535257715908789855472965843348702520429786812438269984958823404891663130729553174190318618369244805620926056726793164494171458005566073667921225278032273826153161288499622926309493485521412662771073810261266710425635206951135223993821117251138192004603103877139981132075829815996439418585511531000220704301232562500727059117438926348657164660687543031771486445468027540614436320792393500127538821559092061070066993144013216722468115712654648183950228780878428996659017799463497254215284953633237735847541261714327033604096042356690010925328542862207086269830500890858967759013160901897726368269631620064377884316173509982974015650187973158968140156739733593348606909594047432829966741262335997402793943495134892775077385368166801906939940678166662533261745730239708338966605788645780899861939539356626355613930832310209348624980668944423177949515101281951834453225762543070983139429520177026845090811897536546189566266973343496625920868