C++の練習を兼ねて, AtCoder Beginner Contest 164 の 問題D (D – Multiple of 2019) を解いてみた.
■感想.
1. 方針を決めるのに時間かかったものの, AC版となったので, 良かったと思う.
2. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 164 解説をご覧下さい.
■C++版プログラム(問題D/AC版).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <bits/stdc++.h> using namespace std; using LL = long long; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) int r[202020], t[202020]; LL m[2020]; int main(){ // 1. 入力情報. char c[202020]; scanf("%s", c); int l = strlen(c); // 2. 10 の 冪乗 について, 2019 で 割った余りを保存. t[0] = 1; repx(i, 1, 202020) t[i] = 10 * t[i - 1] % 2019; // rep(i, 10) printf("t[%d]=%d\n", i, t[i]); // 3. 2019 で 割った余りを 保存. // i文字目までで, 2019で割った余りを保存. repr(i, l - 1, 0){ r[i] = r[i + 1] + (c[i] - '0') * t[l - 1 - i]; r[i] %= 2019; } // rep(i, l + 1) printf("r[%d]=%d\n", i, r[i]); // 4. 余りの個数を集計. rep(i, l + 1) m[r[i]]++; // 5. 条件を満たす整数の組は? LL ans = 0; rep(i, 2020) ans += m[i] * (m[i] - 1LL) / 2LL; // 6. 出力. printf("%lld\n", ans); return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
[入力例] 1817181712114 [出力例] 3 ※AtCoderテストケースより [入力例] 14282668646 [出力例] 2 ※AtCoderテストケースより [入力例] 2119 [出力例] 0 ※AtCoderテストケースより [入力例] 5927561483499133816681483285962193978296762292135521819997344122591819263711514166282293149468917732931372373582374231754637521338415522734986783746251827878858734285992236975761669764917192519634598499956141881618566486524156655583242728247725527832955998571927419919664517757174362165539848928432818819783288418317797891449995554482781481393773592238658854731667832175299162387233899479317587693629389288842517584816558249714533418663147625787276558616452141341356183268829976755771374161469264246991695389539282469276854743339244587176376811562583349151716683359386276825445915243943354271813118549572889596242256983768973299179492513813963166548373125884168652873488175139512567463419394877115371555596287468718681524769631398116896779714269685182377121875661883216277146935177167586657246684288426748585746111476633777625397857847791227846447781527652718365152611432287777972799773917717781292899491177181763659662268342866844661496823674993676359949711779674315715974281427356378439739315378244 [出力例] 211 [入力例] 97228238287242445316297743562293571698136258547357947664137676744787922269777911237528513861156186597324215846711127225828383558398319668244438459791753997581456126356261444731242776625764281311725613586397355614863752185811558675894635782967131872611431961158726691611425372722522665562681397975849497213965444742673553893915738645335128683673445578328225595493367171282659242892738752912911295787728215545426317145765628211362272374621969166257832285662363327561255897553853755271682266589525832262998889511715134226227154168212957786988328833191116875523548248455337535768365192923268929249874252126353512169866142966837557181422476466664955338134995881877252549618484182117218174122345398527169659642974627611471686184974374711987267623722773168192325477251751112133853763142417349415588322718385649659277221955384597588288176942628819731316544956935313883188633594571632613627766446643344927916349262771849311952587942677424288597585719968582134592698486959177783652764624175377469794827765346732911681649683413359145657988387492643414545325548837665575782416266892673692242364852675888531883526188461253945634113343286132513753585429947347372182593937985691453898465646446328747476274628154626297728935929953963898585918952811194147453916579168677672849821641933797722838938131542725837493913632992868367511339571668683828757739439956776122533293988889366784276374449214611872968942766922197779245996138537356134544698285131447816325558292577977548997853545522541448564824254479552321573399161123858827775385673488888495171737135739813928898754687367471134342693644164131174171545574941826528427248586426552437675241235972977272345518584125696796554613138697921324262591952918769893453287613249588119729333127965727212523556327126578141191375412541173713993162573285279976924655946263372519781349757669742328633567424128564312983372961442361631729926886814765664416273472295425554788847482942948379576435668296624794167157396645865427116931783746691476553952571459849762988567564214879132449873556937523212355725797428589474797685711535266513659394965935668687213882692816114744615356364781193973474619154221235759458314558489459818965936398842619375793188515872183129862358876577169777912757425334157419846998291713446764485567616995892432831774597473521269819277463276769345974943498375191863972984823235142339889637588736784269885985178552494447613562928448216147945673917615598679589629253937317614917195696198885316852914554918923238714647639513723477973155731356137112939947447454199248156415441747484149628483197329943878929171175788144434732954751896639559581292591957192638738932366443292999897583481226822891974225397453736381741998794469259947943421485918733756913221337924182313664899545531347374627619465397854734563419612962411255119972155175329931192982535934679935817947879265869983716856415652318195538225753828974793188889555569586176645879365184938433548174975733475178135257787886319618655824223462264769987925648418787766388455684643635816723297682311411587958118557972187116388476365933846454153362762238752759236612132584938618487639823343284949381224833396899911947775327981843262267362719922371877171585449155587545165176552397735931948777996667366677518287742189283451238862721982492612381753749972918459915757555275584426511598563278658311551589383488445451524985579351172293185142483352644298691416337389149215939353432317873623126293968676899498552693579268721435763459196423676442256957975362317726757864711193656262441342285212133985684361254816834143942551699442713829821876946336457868557937447545824455676834126317469182728672178557721544161737438235514642948656468391636319523116282696412734467791264413588474768494392835243221588166749523645165749472568641872764471849417478877454129149549518369989338692421774463976846343183935668135331961583712358461389781711724313474268117692477213625547261341363439281529343523788281942466236422758367325758213943348125311549725776431347671831847574929543284595844629115775117425823339744265127713698168615416336529916877581271688657217772772435329644139157618137634485387723415565646432779293522887785156918468698516218614156274927973235896957571974791524816269874973671959444618289434314627755921979641898942733647766815622882772532495253578612768527242213782636572443917973346391873358554189786439549173297542257457134627899514861847733767584125193843272652244466828835422452486492353835634625832342443536365222222288973721854255556685515895826221239521875471163879644365468485892466864739371584695792168599647968337932994954135341266123577555648515777656789918858723999514782758128383895895882648244295599999331123488235421364424247863674626585546875693179888692886778561772126339861922952724187529467443533224559739134238214389158953211824727428645523684638663959614215634286796921985531546371114983389237869757514117439656498279733918869886253524876447165831113865315312634612817552774589541182855661786459353989634922818962858643144565765531828745374841759773978732631399712455296473473552914328121479323762592182 [出力例] 6199 [入力例] 7659183897322581891441989417986522374719288564486137788587674721377878883159646365746363295255165129311581347555687884227489157749189591898738479514317888816248967165179829283276392434515956864326728221229728881257776356664878151211974914556868799938983352133475239727528421484656773281212727248642975331924732498222379128527119286615753355876978129291294846951793899362666563268474157666719546578474784124934184364866482226411334895149385186482573319694335391552913622269474868443726149576378754894269828835275524388692222346735534682281374644484574418711874514877756255212275792495739718226521827867537426952561597794785168763896168361352586881641572159283855129653847599888739264822278846934248972139944957676353334227121173448665127884696983933297885632168751861931155176281879546699648134131362739137317563564868435252661715479846149666181226718955959184398458596836155838232871169673863145224918563958187747631635155127437847679765347137373613385993619299314428364783212512678498836453297143981184695499798225152175649338675359279762274321564465678287316537447492174867579714232538435151468162472762564798948341138783847132856655672288638789918218672423359565556926812879113627929597664521446687895722863346417892781952917446229641769457337257952191472355468332969175769283815595636755423127835879669651575774415771954536781788862525939683915965495515994651825178797161978793589713917852215953263174812399976861948192875565146794919757651235237941319161711515966124265817755129852746179111712775762121952541557986275243758243696141818686275549522675973938133534244676293177165927825736182674177736526811242477111885163337212821696438241498992189559169598399149776884174121662446468818868465817322497833191567181764783215143315598873958481824725493435566592825841657234696365485222648892166481952517229591639529423588217345951872984864351734186334327735814288334563757759556411276219337386575153444739728375537487937693539223598146494698938113179331921239349493956472668989143812365898711398724693572739485475432259573622128597565438285271443215233216116634588855911514324495767311988688797877653539598383513826754632137458764233637852659848382751522189497287911598128491556467671944167396435591256746466685298727167414385649981543941632293441135938747687883175579177625367916944212353193383282699829214313573518355923575692126394947311582697946423543156566649766411861615895513972937467375734156199354532141982184164418259585184715924488388593893644292825257425673999732121341963671336995852288421545224663395854991889513488519712245932548118714291893685249331286356265485392659357695294417958549197441934521535866479761228292527845912991132768679437843847833591628661373269961622857945624553212744855818932341821631997186932896462661247523174154525586811625569731452977713883435833833769271458299657452826774267839887366337527279529566789794861799248241851521366467684926532819286458492812367714869251417654712139654251542628418491754794196457632171149687232834863416276667918726759743899478235853216545334373297655583472861964662258885589437363335877823743243189748711785468518223351943135516444361684123985611474787168356819531541671615541898814141984491843827163841885864875333472559226176927866296383258957732185484586862627287331274121648812366776824128494656761431678163181378356233991261943836757645747376122374846631245472966579218459377149617714334118452615777375765774158833335619853412316646696136838376317314214752711698946893965422252652961253615617566475933758368796587757726878118539882414652713296541451311584116363188723365262477631238378833384894456127275457498781546336764472563125541488862836713368531976241562636299927592272186783219374764137455774341916957622224457543523916578831134443275173552655558617789968262515739796869854863666133536698211981692336914755656771981132582631252499648898827938848734887948879678126676449936832957342661137625496372992171969281916713445999413935742213242327438511557443183872287655737768515839247873731759186359987424876834142423517944568986996448125425427257996412385337613285898736295817358494797772845711446783446728155768799658443363952285437724678126947168316924149858624237646695154112619957654213434323162128571989844146262959625549949368144862595742467191245232876661128826848371521393518343529755573596743813196123624159223817645558137571547614828451916365542515478488891444366719983288294947476976764174662293119552922632993749439862263198567758533521933794312113465254261131416187675851513336696958284738244411836274552228654749411469332797189891526542869957454776778334693133694597752823582988383821151279356291459653445982511732296335392136377265887912734332545153971526451528111326675533744577593944395571724375543761638269832394883553187676987343497657837759454379794771323621985491498677256322793168178487471353217742272279567142764931236819773792235221351714365256436788674531828537132981799158511184952458334366314476628726775871162698169597661342276529294185932212977855992614552357377296656182822915166432962273445211758182981924982284762143973853766482688712661919669641283885769981893284287622565557994571729299629645758964653876147248746672879834948928668768954783754353864676236331496613788153533636368588143847877171598649493762621256654677897234967435513698755465783485749439337734833725316453326673439826259284741753142371887437333524486385456438624758245672858111144628183529385554228576217994922215465491561577838883987928276899971495998261584325634392914722794811269449271272426481933554215625238941982536524896535498293827484442827343192712687835918666663532856658256312967673256753468829718816599655813277233424659818456265181966286672169633266848588364136572978161846945519551821431826174772451553777756165338713841355365746326334267937632789735548194471733938323842392792872572334114322578868396497657174458448222117597975398774729157618612869994331848822155474186433426839456574529823361495559573842748993736574463127179367665535361685645541993893975951533185821897171769459562882299814477366394744935187967923612468552295928821881289948588725256775969242512682274484129654979268841482718421355445728657299745417366771884141114558764931729334967196513514636983653739881385536447975921553219216473258286635448244515638937529923922637669396123761712741797622438835777131746317546665421671394734173152328313813421787512593655336478931415871697138898361212813764836327217569847519267917321794211671329996538778241967786869652733366576979616293357672831848872838157899571618444395437968133229317145871983584328712463322512328114224832783254333749918515738775396571461646413338712417461327645799463444584852928414328267466454446783395857176455333635223824488399717162215349229984686699181655788999647994515866293879677361839682576982914484612424255623672813914273881856322864129337358591635479167989341264452746428786117313748162598556619964778946963873388332939797291487851869444976231781623364519878961179952165441352748346375774924552896991959287619748112973226576839669568337565916339681211258218959418845332393132977869121732467692645531389382511548736145338717111342917194878784351754629674177315983713159687787736552712771794836684213953922152182286877768371124526452339989915299624739425557922669828318369452982423695734393795644524462716421963573245873295133882643166911131561213281568525996387573376688398346238184841444558259977452163641473589869325772641334222414552498868664381853164287895359412817116579863352615629738467792425267865535937724959687858379632376937611499643124713647859697296134512755281573585921831672263229314574232648412294211277827446588679662665443167183456921642221948766553773457615785377387559245456468775628988278814793621887499434934762884949791552373313715622184748764732544818627471726926755892776696275771875196587145934591844771494411293528331393186253171441687793695393414892312548287949749167861519582458657957462973418288145632411916812417582145252114624689379511976444526467391167631957592389334276872719475463497913458672388634234461265852816461755259634559642689854685496515229776944921928743548699654943622111815266367374293423473514964418527443966179964416957281361263549494287752433281185651594893852231441455267363954987753239631343662986323512259749294141157829741792554788472755325233965396449185788425295756577783623552311573882428338591817771571653933954954856777613212122753641145376495747442979941127986386813636554816772856948337953952639242971354636379172812323284251292794351522136179139464943968598293553913864746716128624258598683213311575967591454113517299765546414543919816683711355967877787549884262242627732597195824288756241994278166691596374926953186789863534178969543421764488834181751813237158179838779278328591817372634663338186545346537294356551546279911577475348774972596446845458513962996572425411122691922689821964655667294544563133286758744829441957432194484851926374687167979339443678127361284393444628319452828717648527661338939651158546337271584737637163297366442799276227657654354696889832559678569496263663752862364526636155781626529447526162253975689848799348857767272814319653727859334573347541868529734989421416966642597662355941875741951873693495183552779593959545672517146231884794936873173427415235157291188396298421629538513694137549647752489588258285992715558879972928538496999721968494581931169329665633948676714627449869697546112338386626418982691247944746865374454949189999853261618995752299936544357648339789743916597361265128257281892539633169868162447952176384978166217224558632269493356686838675821431377233494887234861697632711816999326825929497238268797213335259481495157282142276475679374946855216244599667889642648328969747438664447813177633816781548786528851411761594648132219239624752953714811517766329344683983389498969972365766331787183378416719493562311664687865737499895162562282281177971924526331454921959775425157841428358832774235251643216391735182581825466334153948483536744626512265326573979365879285918657274514881685787185144177443985438743376373446634498619192128868891588498365323742249583 [出力例] 24593 |
■参照サイト
AtCoder Beginner Contest 164