紙一重の積み重ね

35歳のエンジニアがなれる最高の自分を目指して、学んだことをこつこつ情報発信するブログです。

【競プロ】初めて1000000007 で割る問題を解いた話 #AtCoder

はじめに

AtCoderの過去問を解いていて、B問題で初めてTLEになりました。 とても勉強になったのでまとめます。

解いた問題

atcoder.jp

TLEになったコード

最初に出したコードはこんな感じ。 素直にループして、最後に10**9 + 7した余りを出しました。

atcoder.jp

そもそも、10**9 + 7ってなに?なんで??? 1000000007の意味があるの???

なぜ 1000000007 なのか?

いろいろ調べたところ、けんちょんさんの記事を見つけました。いつもありがとうございます。

qiita.com

それほど深い理由はなさそうですが

109 より大きい最小の素数で、手頃な素数である (素数であることは「割り算」などで重要) 1000000007 未満の数同士を足しても 32 ビット整数におさまる 1000000007 未満の数同士を掛けても 64 ビット整数におさまる

なるほど。それほど深い理由はないんですね。 素数であるということが特に大事のようです。

TLEになる原因がわからないのでデバッグしてみた

ログを出してみました。

N = gets.to_i
mod = 10**9 + 7
power = 1
(1..N).each do |n|
    puts "1-0 n:" + n.to_s
    power *= n
    puts "1-1 power:" + power.to_s
end
puts power % mod

検証

$ ruby b.rb
100000

原因がわかった!

途中の計算式がめちゃめちゃ大きくなるから。

以下、100000までのループの途中経過です。 8262回の時点で、もはや何桁なのかもわからないPowerになっている ことがわかりました。

1-0 n:8262
1-1 power:14944194029877861130423936771661900007989986729078100830370262895602219261702855651243332827474034050703511262794290622129089573336779337673448852915475854790331621350413426865412060232546779723391583627284390541591998001620099215619991742392497493697705735259452511296069861807921853046386867116721272086718998316594677967513396179084628452469808377597799595716755433260333114888735384321296387933333886403792433875528686988409040745939136422870877787379137824882724705694711759448684021392889843158876850324278458161637151670636549605463076969126017976449896068801482600572490527632093902024074734145744202153456355817818825827016947554618741475725304889494130366916318756687066216379616567444019347065779786536582573696634363767123299786424305321552949004738346894796705966189378469966727561162253042810518611575396423778312805970727099549877118144579882487616500216376460102066448183651175174776517217273616500588167696120806217318114747727920653725510781700359077677077032210807105598585646019117461170601359357763494475356521404284833044801385204082675911175884292865422797880386346474578411442072582583926830049422767561122337531720619914291057138129808247746419722844437230011471301275201247156954302564102818210680743764843033731290528656989805461302430261377063302810999368481181634247511184794973851182795115335505920886392610796097432093962219655741344448266195664352463427645624575158419516182877433639426896953536116816588084634922229200773937077878742628200693661836988259194346916623145641694378719803566454184016261069382184272780435403226588765798615168623773065900921389849495547640836555938701495387507787133044096523595415294346225318760229303787328781665042194195939819637414277584885936249765275073241036681836980438305319910804978567314572018016355297865364900836704743081528546772338429096866575053343808464841719585285575781233543893109631155852896250757555928405386329819196928566119535822573262579516066633419639675116127667379233205198002670142606075346763588638992585636870967838869793277744654340636419270514193074813840260101924078598511936589336675370531145969724778854267677102831692358499023885386117027315393522283553303047904649002342642895049809610893632458789497275307775916798309619710410582586773209358332103393107754552557076745574540552725351482965103044334660015100235716166091917600377627402566657888752390865029218103800745117906010828074850991701541289984215373137003499609069543400531221007755142492924708027606645422516007637396576297030647377608960679215221728864257604697969630542729214539416787957220770682925903518313688140933748640277161313291731858782030871607251241156946148025807483249673020768033611463848300857517624558197327290380380098664337791173415771449561341296258294047666383454628958302962149441394440011406119671391863180604951138504371638426526208863072612865077287295154028362677969970794655507139238168558287988473164968444613837775787184107383822360160401452292036585328823180676922076205555085744073889659375445913609371244014430328311333032718175977250662146725939623463707652846066831906887580654450133621257546009437682155978371777760768035094196456865248163934646823310120529389836544357329265666637702956448472038940950505701461319140063720426158362661365768175379745940347390573502135966990364766269012329297867265560044524871667498510942043101183404779295507437368373586021462623191810981340197360762661147480007309217180630230675094642469769665868751402221393596028468404897718682170173946528138326004559138867793827001092372683286050839082652017590775313519539297538542908206872599352665690146108657553455286338435860284846918451202270689045349397006020381070900243040670594346513711989203580301492799793452712476588358951741949081718741838917268845615176171879955552786045403809457982553428193224440143901107291923376148151341863390620211474288213186693499057133776531076956259092731448581563281116487141281284247757159676939474407936093177328391466731934229860532267005458975264645390007692678746929862870675904768935767866544762931162345101869211009503849078113233871449636165910796773721154364122228152344058974352695111044136854110994459203779176233653640145034135515486143018251733496174461002965646531847888152523538040259252085487697172886218931696353378617131656275311733335375049318855330968359097888648837459904133900838161517537843556039871660145727098081956267275540991609363122674934846215497919914604973142460344784409784835057318692211117786534493879907124023140768170219659069978642247822656996820480649077332836418597526373487283777644396887970014394907627998966000339051803927288255784865077172581135601439452908642751677058816408996725923507316603021806351678580463174919625457130427663548224815190860619486055149085464547299053033056106089786857998076337254344589027587818298722725050881132560659918430452080730206033842848587380085018690604879164541224198389582354201915266338613957784867548946591451480868306246772942686027591635239478351047852674672361952035506681681104487464790160426103708066151827391611138832399336813831704396870351192543624275465622686380175443411917892156635488865119800603760129800216535552287686104937173233762316199184432896989474907176902553136824879321706807642366815814620201063993812227173532269310619290403216019432630782708726774564877552457925727804870780258752895409152992598759941638855314687807721304721664068006219067218291327122278729234201284513899147203438627298119845729525892861389304785286934975800942295314612752962694800418129497550078065192032676477177067746442547670865521413311741919071206674381238805878929690274479524132417744996615211713663342293077278697148038905409196168564649500392997565121243587879241151213362217677124850165762787053359800099384492710666018117965118784915247671373550083575007896599014494205508362146749460963031180188477432218082538443064863227512425187274373831445100549032160726508278531929587801688623229633661635156109312117092443356059356845595163318010735094176074213451404697605428024243542331358163169053781994454756845673928809701562694730325698986452858815786072742864363564393638627625065904068542909847935250707924553424647032902975844601796203073290676499699551133408169610733233896572164132595298874897151209065106120537723177145214214199128565233046137437824706893847682111909991527610806519087091477787803469924113507169584079454822477511059880927388698205949936024349901742707609613212308668665704083837660856133828613969863861978775697340318977679741757533148304567619496705442542946820823747165314912739283226543519773777381393260673445394402018426573327511326892579627285262829286002118365645611954357217042040979734430591759471314839185930164734594153890155811193928100078693771716632114609218966950407564528306682705682754773127631154141079316081876755784170952459346763331908270333560194347505029633905901098311834815798432603593107049016142507608000711266448360589126516815049948424337688848865029640431890170434711468812626324637747707519373745985542776231571619421778723524468829573771163996175653298297214628441270579286615176141859549908191291432561426881121829347230008935308153030100066783746031245000171230061645481553853819196140972156272712989667932232576603767769746115323162998287811489240731121184331256823401282808303794387966900040099109132966582997597932977767326038393375807006440814757020296945728980662738704612356575633721850399813083620348621582509803871000672182611098518275158304543308240291127026613521356317307306101394303663200093541614122331781823998547175442076048439205256117277123995012839860766385239861227534530795345084752503961247867886250332991766765693844740079704433672218591877667647452139221711713331851436195527244289954169284863542191258231940567908914743479819979752280847662898699856789066367513432105804160334342045624507006241311808319618032986969731137423269689948343961156819098592721134395936917011921105850924136024826766507269700035523897844579816968605009728494069112514202049366377697245783930316354328787479971599609060467493341503595515709820226113843511301573619454243528361967534888298219278935025608857664414122937992949871155266296596475210978422750483325400585391492000690093867539286258192689013316952619050900361838932281869619248730525726684047944641826495713460635047066293378597149234338233097891421278072341989056657117008057178684605953763660613571748881652079011422600815449891416634569063674809476402599958824783098378621500836523264199075187573907198849302225384494718837440424185612878632707364894927650396525462147739663107076261037055623383508801157234730074514960069220261572544579246686203269228634897993360161163574617999326125942054644573089515827914299852577056342230949814441450511492951424064003212923721784893692547674713431581540228540075063566021002199101851961276295650033932059502229482204384569541258736249457112962457356263093451667265305327139689740569333912552311540792711777676667676060162127651341096086611297197450500866268916447354174838881365815490451536730741416534618423808132617305518024622650201027460551762975605413174358063134909206916886055054067042260375143283956796417506879798070453565919449434867749472793348748191251641236376345798712978176520711866118645188914779944998187381303668691103983189415387706863737459714435061893643800713067416817841037184843546043610758686010398863683201186115624361977623466508472000118496571289948503597318970773294119544160606377545399045086150820021150881201068999204309624536076775220234609345488513168780276088789873626845562379018299711388993681380606597451006630622632396822232543672349426724722583708039584706415275689689379329999111531312062760746439311649312011216624943612929654919812467603131742960374282310326309379793988788460195610458606927959095984580405369117980105716090004116081352911879321945777170150502249598430691822410169590231118376383789799194273302364470874416434160734223719060459262569829028530024648736153680397415553452127682897624545367616308272362754789373844113159692607077441946619359273792999950323148784352338647396682670110775138448081437428363415541405729777494014034317772224231830317336310500289087441647872398776537676794637830756972158854318554758637613282155167752345613645343935187542279341557790599040806939575076249389042562474917640183001862058502350135590167746727341946158117650152451222050309344193506648409745126895447436826042461522302726060485503605795986781894480828065626476770282246619916595289753979704421759589344622421732923097306523503962567910712202686576461296885668860965884271676777676482282318250808520764442982614493742575278409757401314685448523542721669210641192167515228614194547354655015724394384471144117966037974514545210867898449779432754424859945392537820982126190216052172748310206941616607937572021595347048449486753252048175731613093716221911636531339844107073704329884846129393326539403299319364541532980695498640772964272817566742050897898397784633336799071042336493766548620300801500868517699510357831435994156597116717022060892776527547357652192644530471069929051904074600768721915186857555002540619140842502806336666000738938445226398165900929414365402533450468708380777896754774068140921409879258129219944433362008450886675707906597583456424697598591217790145209586290307398397478168375151779100353619844302003104781278063726142112000335611511732931176960573490014596939360990939673827575042299531400284903611022185665071735882938379558704770589393401914188465178559239599764738974488006248407345741030087259725289606856758267847787101716188819618354333087486023983609606724129114928835415186342563848691718806093685413828198793839238172603760725749440343188578405828538208914100453640322259450612491950922252943353228634032893875903373682263626006734748021043094080444927629872109205928083827226545532538589568048707455034706385700277552084179777396363963775282314579633959383193350645381933391906608678557861023240128128338170854546699927940933954786758641891758283289730693746525259471024642930746683259813902675693903545580415616392113401696313522380526528149429578716978817012303037345508950195904158089403240108027917529310610219296438820965149771246929938548219744490278363310454958981833127367810604295949378770188822481683098794960351573664090483750090346637636531462440356189587636427768995458124109134202658252914053376493123395882526143496984727819063534014032072557903976381573297914195487774899384574965153560565210856522752255997788943806341491614292973852752040214923058662090920080318355589884634283088680656665557996989867504963581187867908378511492055775148133350127562385752832780447760380774303285764160066035112935931010839321112029198221186171149689549053422262261072394036538958187141940770552841056413765885619818658721800374483849326761953871121145878195735246278883334495398319666547906218152647034910418664866741017733313179743366061947634691857888408467851673062515817427732796028311778415653640383476516494865224864069019965643412496259290155892683265267562611931876162482373304655437127713391969442582009629442633656329299593893169405143381348267944757718964988463235294134342165675120132823497134961827863256381284497401912842460628992913585806623122093843154187775220521814975914862055474715305599934762802052245484268201953034129370029431255169916121936254431383921024529971375678413528699352829367116358971737954813711902162997635830768410681429798795714275910625850300025778290047643340547120130460058068343979721730869810994935485837125544878131324836542842498812046535107544193602499014897951259073896217932646668235525855620485695401337021663121188438588205362120973544283522092161072025567333176866065727103001184795260138711094864570131062532051546614629215879828097137497956198299402240458993937564223806451885297501428505936312870733701903111059889570512445828588999074978253611429205621004243139518998406390842517343684282591258753292295168243865647069275836292413016673208687780464710442736320922784247863258250869786106038789063097530795374899346417033469953647183824936184522949054855695653906652294074026059206109501139933226114012733146996839516488390480927348049907498175873884440748389075315514947607421187240276478212097162362798333543827236414178033337888924105240011402614396359587259505746996477367453792791797128984831935250909202608119147033459791240269616588981513480480930297884211894935859723606345450470851196765394280840774456253050619055274808720247277639055502085445773370250326075266102801039683841525330492493539419024740939534509650401146619452334914683561823673384281717470330657255932980191762528640193779028716681572593114041292907078073769005621127972309582271948413305376333222551056985917740076717218654605218455892606871906959135423163039567208108373139311304300993264248210815264135511673053348559275262462017261195708649056161418383864874393267223472957753117832592860889615392991518191561824716954886340337831018837434479925753885899998725910174298817563579374284188360456994574193249267640468879034804932059745812128148433302208373734817886358243778519589451627365749638437715581839688989903844432402446106128190599115472238769797967845898468420808870387836517924415705151299940817483893470214537187238816658161126116943447065778898731001949545112186299552854974307790239629635336576338262693370574442168638928746476029321688715236837947862712589501637407347535958309191571840874354272859976242846562963293920929099015255335721893507226401205628323084947133795815096389127577466770517493209744641278215444345589296652312287991803091432744708155055056150587369967468061553696362232654993126262319427182272686828312159670456348509414648578624406494736365276651805858394161801606717884912396456065522156864611955200280183138983196385978077190965840562860780076898126288143401176134840070249291656891940458957864014166230649953389319858112711678848100115684431865053850988638037207927651995533668237758794547508547726823332917699317041040138269300460535612973838470612725022045402895985753827358633827013342031497324140403711077570150283206276339254766951411130559434719470464792376735599084623350945353352540912016080642093569128795448423040074503709877640879214490243211275115421203621932366320699239441908049576915093002162032919585930112205567546483529759795694972892380536047436378682498577064699803630185094067555998461837265376435130272773033207197764803076038968841005253664851985543508442788144857511975178949065398518270357963070142809524952006173821964864494243573358621403079174143845233615600362332201182962760018533112770266684903737947669696376443399731192671245022805536274426209093852135761638418634196070995307275784764916579148498080138372800532293860042994443506055403781696738010787690394845951696980917982735051193440713094971017806538172392061664947264876421898314473946471058640613876390975059420861877075055734391807233070684302648367552483675615603884211627017180828335693852937533262588549836814550314265274186535914503620643395845144722934368649511749017636557548498721382236677393699633216526995587449819271389872136317202209573514275543084284171878709726926129648508015863696171033360267672515860924850859512430035142087261062471447725539710655725541891314487946331766209176914288153861112170654053755757850921636513808675775406946570232130344826865362259750783413284383045177652839867035504962719313758342921846244759588328382093823086918942823885736602441454095012414182791003016438544449544844953122938754370594635936597368862704748626120041960754988537970318276887098478713723513164440955894736959340504012307643611315377782799206728048295867383265521953433814917892050873734174543855927277116603339732142793893802893779726686726165243391533655849865120559714648522474188202552232761177895883264507906436700317053706753823227798809828465332046311406287174607759908311262615719617593962368026302014678251343461251841192847895049563229165816539616583354083529689498081550797143507536030841630746177791525457929623364940100135251830051388961006670589496721533287476954156729739795892800369439276423005481609605661733216462784776720453819830167307348455799268546412575576637445167711684968357024467795367040752502103424043092149605934734909692050066047432012613045347017576269491331680096530621111283256550046059279423201834169461038482604850780013979202880240797221122804540375299523099118232339207368703420171000659399572385497134956030994499128563211880236440541018592228680509758970077338965767232209190161137906938356494721353885819407488154209371800282970391735607701206429122566640024686670719553969755600895927577667324387316785301360753320693079609616085758957653041328501423113576285737887036155972756420796207318688695693359553207666318107542176264755422850699460779124307533426542900331171739388803797914177614937901892575193853350844848504967857722097842265024050130796033769274036553111801561372606215913091243511109400800161284700210443154300322572589742768834857107177227267027676748821394529758586662128027283888749938965684774883798685578453857272998344590029202211761017984803997150924730735573882647325495679137019438706692285149745049782007647132556060574866106768557204211067801471847938327855065172195950504879846561596050994118413473703179621141053144873489034958386994400064848595134414808536974480663515060967076198597769779760200325254644025977020164874610181484333153282003188545355440265767763566098312406661215687980202640472333472060342852952699766640945392414742454392160369632157073406526478480142374893191896149967767680816913663858936917896013467024143944439002650676017306531217895647664269504156235171555365988456111104420754831693297121883420027282009378966505804888464168813196006453536921918470480963152938432181474218174148540985594837182116722926017385726137575747681750091428097260718617770973650810673423593351832376391446430651409834081378946653513760978769098974917944061661168478268211324374253213452247107948974950686343538176699645155514967614665354493565321383455940484406592137625082252876004764986888785961430311307299599319770539386019251665183285696175445312777476388410452512282917803995311777467060920027680340114370463651195639495518683209321172914230255011740190931894065308258015144276527196335043113813106029844099419749918114318330682154977966794555866082515600670427673649267769962751257846864625386023777663996858455795393278394062540339812062038485142121114391188562516061848564354201434015501078506621295143682100882075441591274374292077067869341846502670834229430262746760732007316518562311206776881926165440867077067624170556577077491258815861271937556433728375442948156880298701989352780445739519039473390627610686429448031413321048822646572302111547848572247755890074057341808582626014444286454167233462604413728974119497318158867284752021514874152451471887252540145653237236936010072204411890626583152604671823340986850785820275896083405951340968550776627708827647893663760026541125117380379447177777684192728087184012210470029514966000481600132736308738590387872222679627608126981306432567281000928183322664017445441690657073792070401401181261439511236501899160342619300719766836091451026136421887407361607285123144703584452911562998451737748224923276688978935816260433153374209787094560601186672573190649949984951770419059669612194221167517868410551282461557417561284578108652987703294687850456261406444817919018384054429494712677365075094462704981454053348071170118540290133838368963947365990219390442538900304948275352285036093990011373629315617800587611663338588320244971810708859350480252816387888046133004730379400756859958568224303589987323460213411022191811859883670802732025121439900398941921013662590058308723411025708912791584656393201410958661110958865673219178994337808660690969011332145751632592962526407777954786629650314423613533027961052498467297354772550557128710666516863434482400402570872496066390674410453854394191104971407012962218989239052449088482438279279516349757847339762529696568346431186484471322479773164961505580584475261086144020084340547015131001632351628415375605408240456559543129313194728235773318420020436023701715891464295620288662770964387457304491677616169235037564422751016410247386537135787006970647911569272673319911822979962669255034327895189353230535441706488592396596042842476401190341773359399762832595954092605390985284875891805891177457255084016052331124801023921474381624873172891573510489421818259660621641816881855300367847727782712455317685161027407697001653457843572161710152883846991401811651540367503436658056572929013492814222039042022155627020096385519220989389346837580843721572486802372857870639270707501295494847505706642822063923003672649356910016659906377876044422767761659052467707093608993415937716026924236734051777827536437758794956614232152761323753592957339347583442198181845611600105862780754483472461706353254781403783737445463255455912461077943783599324051642643116082877422015197364611447330912974993270147187956114180299297488199316796377025228717716421848540638728942697440515129844984390850004585661487333178499059590288485650684789837021392126129148321067061298410085042199204446000728786237784189490395874440561334872311158337702236519258193167826687808999129969109946489979207911894084533664625164607421680942982511769614193081074990285853958531781404453939639548308998325948783564901052894677932837626661999637732287971982768537504259469335248658835624459648132613056224999475068602655241635272260340504565199922904677336249190556777996952282916516754477556411828663191117041149042870639788043231840415093904511569643683113302516978768535284524217200315838945956909357676192781524928216119624515296201948168755809439627948506030181324239475845251761515551693301717376070558303880856075745315156500913386081819092260497946863215400172835700002048550772096872634632203009821836992589467671058729182496784003803127426492722422167225997702321096894487870542951782213555485477149943354091264395076493273655865951729934549521268897362690883522526982465522691137149309555520025068590876932066739468470068562693621476978962787027712054744927438818374022580509435591239379957567881002247030945877692738223079033649637967257930725315094735343621410957923371917815155654421939418113116375020755300525450758328737967063001818917252884358947865735289011412017061418755461157596292497935651524507222819630044840839134498462868557386489058384209356289256473104504354716846257717895931184168824700193009308714783827548423427722768783794595092302491053991112518087791742335237659533495614573969969787901452299320137810121025207869394766298329704186881130996784781103090986293913294932194241605110429449343142216123569968697041975383455529284116800440416000552006450391295998484215300747620139691879807274785761534463295809454945756323376251828058939421420816853899355590451146070579226589239562316418594593677034246566656521743081576094806680916595276980044935474255725230831007973965769854205362338872008699589779442807453612351947649659334998927747515459764356617181757292785868157888623701830824368299932371354451211938736204520315189116763469749795183246447641897892901626714632268943535730246717387021549553069192798593158465638928224117505521472384166948070690166015104778670909855406734825201966800606449615986605495328629397318139987789423014599726526790122298067609572276437380111295591913431676406550429124625342348026183627557568486949011590078029657730862044611210723620508398302234199178136199112353370412354220790804963051084155096920041015541475632319297439423416251921788134338262410019113012105551828138374255647328229607628043962648724497872819533167606570429293221520370243487895233564333589426401539136152057944389002626444161499991600288300656901819621630416982520339088607374798019446249161805542579314113815590060672084403614690200339862060202732856970706815450365766448472406104381341076848224994017228012600317882166325614690503222825677844163845658751238781873687163290235376088977289759081349573660178553922885069407616924258404599181595592692639458153539978721899053584015459192688848787187637570106496797313934100691568552895305119378917772503861762538649971182285062021387197249763254431475212896027849815786464985942673848063063747785046623868879089963880379569413367095505585361666342442647069796540000333450646412627032414331801782528971593214685026338905827523846156197821839579277446211548288578511690618886946620554651252467591295845363387866211212974025337202218181694426815599328433078191327018777306953730833446329824842153634504465332518883574514905920747751471203198632050384682087569493940036858739003988181404249957617410716075853045804413581422298177411738436192889230666848394555573149458270640308911246746575491562554873447814484728974656480437286899640145095449943690006933558646965253638306442334184918433595247629561851171750663393380693833682795952891062778996749003254771397883387616764556178778121830400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

解き方のセオリー

まずは簡単な足し算、引き算、掛け算について見て行きます。基本的なノウハウは「計算の途中過程で積極的にあまりをとってよい」ということになります。

正解のコード

けんちょんさんの記事のおかげで無事にACにできました!

atcoder.jp

・・・略・・・
1-0 n:99995
1-1 power:68486475505000
1-2 power:475025598
1-0 n:99996
1-1 power:47500659697608
1-2 power:659365108
1-0 n:99997
1-1 power:65934532704676
1-2 power:532243138
1-0 n:99998
1-1 power:53223249313724
1-2 power:248941163
1-0 n:99999
1-1 power:24893867358837
1-2 power:867184586
1-0 n:100000
1-1 power:86718458600000
1-2 power:457992974
457992974

まとめ

ということで今回は、はじめて「1000000007で割った余り」を求める問題を解きました。 初めてTLEになってしまいましたが、けんちょんさんの記事のおかげで、とても勉強になりました。

他のACの人のコードを見て済ますだけでなく、原因を自分が納得するまで調べることは、とても大事だなと感じました。 引き続き毎日過去問を解いていきます!