競技プログラミング C++で多倍長を使いましょう

1/19に開催されたAtcoderのABC152 E Flattenでこんな問題が出ました。
https://atcoder.jp/contests/abc152/tasks/abc152_e

要するに、
各A[i]の最小公倍数を計算し、各A[i]を各A[i]の最小公倍数で割ったものを足し合わせる問題です。

MODのややこしさ

modは除算が絡むとややこしかったりします。
a mod m + b mod m = (a + b) mod m  ---  正しい
a mod m - b mod m = (a + b) mod m --- 正しい
(a mod m) * (b mod m) = a * b mod m --- 正しい
(a mod m) / (b mod m) = a / b mod m --- 間違い
今回の問題では最小公倍数を求める過程で、除算が出てくるためややこしいです。

今回、多倍長(boost::multiprecision)を使ったのでメモします。
※boost::multiprecisionは計算速度はイマイチなので、計算ガリガリ系はフェルマーの小定理や、素因数分解など、別の方法を使ったほうが良いと思います。

インストールしましょう

Atcoderではboost::multiprecisionが使えるのですが、手元環境で使えないと色々苦しいです。本番時はAtcoderのコードテストでガリガリ書いてましたが、次回に備えて環境を整えます。

※ぬるからの環境がlinuxのため、linuxでの手順になります。

公式からboostを落とします。
https://www.boost.org/
バージョンはAtcoderに合わせるか、最新版で良いと思います。
バージョンは各コンテストのフッダーのルールに書いてあります。
※ABC152の場合 https://atcoder.jp/contests/abc152/rules
今回は、現時点で最新版の1.72をインストールしました。

tarとかで展開し、展開したディレクトリの中にあるbootstrap.shを叩きます。
その後、b2というファイルができているので、それを叩きます。

パスを通す

b2が無事に終わると、直下のbootsにファイルができていると思います。
Atcoderでは boost/multiprecision/cpp_int.hpp でincludeすると動くよう、パスが設定されています。それに合わせてincludeパスを設定します。
QtCreatorを使っている場合、.proに

INCLUDEPATH += \
       bootsのあるパス

とかって書けばいいです。

コンパイルしてみる

#include<boost/multiprecision/cpp_int.hpp>
#include<iostream>

using namespace std;
using namespace boost::multiprecision;
//cpp_int 多倍長

signed main(){
   cpp_int A=1;
   cpp_int B=1;
   for(int i=3;i<=10000;i++){
       cout<<i<<"桁目"<<A+B<<endl;
       cpp_int tmp=A+B;
       A=B;
       B=tmp;
   }
}

cpp_int.hppをincludeすることで、整数型の多倍長が使えます。
これはメモリが許す限り、可変的に桁を増やしてくれます。

boost::multiprecision::cpp_intが多倍長の整数になります。

上記はフィボナッチを求めるプログラムです。

9997桁目7942451597835212877603685972178130339871923727351742332801121758376921404744710929699316554976719005601449353913544156647514798050636678089226727896749044189109035127132643621359780763299665130924187324835531810548213155773790580546039336312202344371320804638980155201694436255167001794593229047886602016833240206631900232733251067546890736016966442915913590166940162075762676506973143326435702336579051231813657829913296278520982627075346044720041492038091215036699621641668376621103722462659874560920989625860461124255355529458183829231746813313149481311920220766903062961913182301035641657996171176841720210940872251697972185441060448429491075938871146374619876758089506576567994123446471400044700035130919107718466321788074960905257807935281730672915938609092202664630726743708567262968391585571031717692325457602486278819703636773888335032078218891529882437068825613920361138268695415537226810230819772196420815524824890512344473054712429171287931293919386760678905137574958760619839974827765598230755864034556971572296663139861596181605029681551257631174986930074693178605308400724303797452819419859649928418020026730987478028222323685112337079867183071588576567886998051753579778018770729919243976982730243439253606091120124809969110898533940239171249713139652142831657866571905912649593967889572123639232645383189138008351573181429351089762748601034683835411874910042460949064299801788793809076280527242750594993165251632289933437600939164213146398295714381956337158201398776827711884958459006663883803188169231624347509275697713978783014801589022015669237589328791888635521288580434384602457311603702831166979714290588623947802346031360861616412984961613105122172858676166923102214039588384990241476089383173543482523948193038661574217238673916714310875117911516196504083276989156813952694788949869862714731286615245967361671665747526198135106324680981060122606067150471927560715045066892466960470220869514208676444335116397844135708873616335661765966388784357650810083480042174157285876693131921834789506552960387619709697849853677431999157481483883646472067523133763242529094377
9998桁目12851156639298285194508963016464706485215112366664160786881824108151580018710975719228139479328507509990307989383646001363109996216614295086907082283153693849122754621213591935123410668292259401470232703232278509860511258919672268516629050771105703879599849854360723531531941325680444530280568555848192631424873651999650171347766192834312183926925928026939011480458051478716405316620572103131242812733942433033121260524503006252692752208924615455093172795175162661942390465222979170038150314274206242583967168234187168625210526906534358430922157445387902040757200068671092983745359702599123666544834944170726574748299243105290223161632642782110897999358300261430024773873779583131083756981248889190839294540958075197177097291111564213421048886319166847255131890345454402711674127375341548832584674156400102847228799266974536536214821479509899350282216871229940742827291134503908407655937789076911182619994579822317665398756663476646424096756976960407683203864333982782468618643726346236986115868574217260165389679980270294614941110735757566218703586626924567334253296881133237411381684025512275390763068753534901487363123449060366325529230516461496025654797926535256685374230638070471999827817731160546830845636888945544845702890951759088411260146438722360911145247571740142722617360023628572506832424008564945769953496377325213076247267063213983343847207802717813584548653343648832981334320679079112769325881931610040625051632180272388226841883788324431094419650939177867372485343658626793218311309137706234691718221023310594849628333795898586707635464361149691151005788188357292413937321103250323197560777174351841321360278855378478634068725544232918659819803071386983507166063747567453690351780833706145616828806072613620926438857190639029024372736790739649205053016761755330679939716085671868106634916656771101351634827637128101587414724293131066603823147044161263050273057017868756948233805315140830564210830598544882369143772329659689680193206763021589729329353510232172028230754248549492660220060420898575050174967631334279455256193702309281636610155546262324582771469773408709136249
9999桁目20793608237133498072112648988642836825087036094015903119682945866528501423455686648927456034305226515591757343297190158010624794267250973176133810179902738038231789748346235556483191431591924532394420028067810320408724414693462849062668387083308048250920654493340878733226377580847446324873797603734794648258113858631550404081017260381202919943892370942852601647398213554479081823593715429566945149312993664846779090437799284773675379284270660175134664833266377698642012106891355791141872776934080803504956794094648292880566056364718187662668970758537383352677420835574155945658542003634765324541006121012446785689171494803262408602693091211601973938229446636049901531963286159699077880427720289235539329671877182915643419079186525118678856821600897520171070499437657067342400871083908811800976259727431820539554256869460815355918458253398234382360435762759823179896116748424269545924633204614137992850814352018738480923581553988990897151469406131695614497783720743461373756218685106856826090696339815490921253714537241866911604250597353747823733268178182198509240226955826416016690084749816072843582488613184829905383150180047844353751554201573833105521980998123833253261228689824051777846588461079790807828367132384798451794011076569057522158680378961532160858387223882974380483931929541222100800313580688585002598879566463221427820448492565073106595808837401648996423563386109782045634122467872921845606409174360635618216883812562321664442822952537577492715365321134204530686742435454505103269768144370118494906390254934942358904031509877369722437053383165360388595116980245927935225901537634925654872380877183008301074569444002426436414756905094535072804764684492105680024739914490555904391369218696387092918189246157103450387050229300603241611410707453960080170928277951834763216705242485820801423866526633816082921442883095463259080471819329201710147828025221385656340207489796317663278872207607791034431700112753558813478888727503825389066823098683355695718137867882982111710796422706778536913192342733364556727928018953989153106047379741280794091639429908796650294603536651238230626
10000桁目33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

http://www.suguru.jp/Fibonacci/fib1-10000/fib9001-10000.html
こちらの、すぐる学習塾に記載されていた値と一致していそうなので、問題なく計算できていそうです。

最後に

・boostは他にも色々あるみたいです。使いこなせれば、競プロ力が上がるかも??
・計算速度は遅いので注意です。(足し算や掛け算がO(1)近くではないです。)