No.2193 メガの下１桁
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : 👑
p-adic
/ テスター :
Kazun
shino16
タグ : / 解いたユーザー数 13
作問者 : 👑
p-adic
/ テスター :
Kazun
shino16
問題文最終更新日: 2023-01-13 21:02:38
問題文
入力に非負整数 $M,D,N$ と $2$ 以上 $11$ 以下の整数 $B$ が与えられます。
非負整数 $m$ を $(m+D)^m$ で置き換える変換を $D$ シフト $\triangle$ と呼ぶことにします。
$M$ に $D$ シフト $\triangle$ を $N$ 回施した結果得られる非負整数を $B$ 進法で表記した時の下 $1$ 桁を求めてください。
ただし $0^0$ は $1$ として定義します。
背景
非負整数 $m$ を $m^m$ に送る写像は スタインハウスによる数の表記法 で $\triangle$ と表されます。
またその表記法のモーザーによる拡張である 多角形表記 や日本人のアスター氏による更なる拡張である白アスター表記 でもやはりこの写像を $\triangle$ で表します。
$0$ シフト $\triangle$ が上記の意味の $\triangle$ による変換と一致することから、一般の非負整数 $D$ に対する $D$ シフト $\triangle$ は 上記の意味の $\triangle$ の一般化となります。
入力
入力は次の形式で標準入力から与えられます：
$M$ $D$ $N$ $B$
制約
入力 $M,D,N,B$ は以下の制約を満たします：
- $M$ は $10^{18}$ 以下の非負整数
- $D$ は $10^{18}$ 以下の非負整数
- $N$ は $10^{18}$ 以下の非負整数
- $B$ は $2$ 以上 $11$ 以下の整数
出力
$M$ に $D$ シフト $\triangle$ を $N$ 回施した結果得られる非負整数を $B$ 進法で表記した時の下 $1$ 桁を $1$ 行に出力してください。
ただし出力で使うことができる記号は $0$ から $9$ と $A$ の中から $1$ 文字だけです。
例えば $B = 11$ の時、$2 \times 5$ に等しい数を $B$ 進法で表記した時の下 $1$ 桁は $A$ です。
最後に改行してください。
サンプル
サンプル1
入力
1 0 1 10
出力
1
今回は $D = 0$ であるので、$D$ シフト $\triangle$ はスタインハウスの $\triangle$による変換、つまり非負整数 $m$ を $m^m$ に置き換える変換となります。
$M = 1$ にスタインハウスの $\triangle$ を $1$ 回施すと $M$ が $M^M = 1$ に置き換わります。
$1$ を十進法で表した時の下 $1$ 桁は $1$ なので、$1$が答えとなります。サンプル2
入力
2 0 2 10
出力
6
今回も $D = 0$ であるので、$D$ シフト $\triangle$ はスタインハウスの $\triangle$による変換、つまり非負整数 $m$ を $m^m$ に置き換える変換となります。
$M = 2$ にスタインハウスの $\triangle$ を $1$ 回施すと $M$ が $M^M = 4$ に置き換わります。
今回は $N = 2$ ですのでもう $1$ 回変換をします。
置き換わった $M = 4$ にスタインハウスの $\triangle$ を $1$ 回施すと $M$ が $M^M = 256$ に置き換わります。
$256$ を十進法で表した時の下 $1$ 桁は $6$ なので、$6$が答えとなります。
サンプル3
入力
1 9 1 11
出力
A
$M = 1$ に $D = 9$ シフト $\triangle$ を $1$ 回施すと $M$ が $(M+D)^M = 10$ に置き換わります。
今回は $N = 1$ ですので変換はこれで終わりとなります。
$B = 11$ であり、$10$ を $B$ 進法で表した時の下 $1$ 桁は $A$ なので、$A$が答えとなります。
サンプル4
入力
256 0 256 10
出力
6
今回も $D = 0$ であるので、$D$ シフト $\triangle$ はスタインハウスの $\triangle$による変換、つまり非負整数 $m$ を $m^m$ に置き換える変換となります。
$M = 256$ にスタインハウスの $\triangle$ を $256$ 回施して得られる数はメガと呼ばれています。
今回は $N = 1$ ですので変換はこれで終わりとなります。
日本人のふぃっしゅ氏の計算によると、メガを十進法で表した時の下 $10000$ 桁は
7180405365660215029635861386593490877199341264645292748632958915468276962111262181845086951433494278924441156737858954931746559518343231287873346981964819909619010564056835703607406658716970443101993370619908539445147212210547752751107044529537696454207473519753221267147643598069213507222848077584718927989238138376405834842836004172595384149729028393248912772665073380791542100007517029672997233631576749843120577725681662819813529215553075032438180356014628513078390153220696337552232736713881101667111456853932594430937430003704034126564595914803794286846144578253355465749795834167865320597891439492014463970197556870759823793940777859720656822407781539160756761027513637287610005271868499467927495019574284400653744429408918464083987786271711590135565783528117134046845089395381075547115998114262498805433619422645670005844832183399439455338703752357401385165492738569513641267625952256239563639489837683676843782802314867721195489301758689328946923663604035557569334247855888586259787642618607363964681122379852522060462258854905044862876435800039810504578808537009444493804785288609834618558803019115988745354135909324533896852981454373912053672732595283351129885527791718126868540861944983204252358236303220177018544154840106209670565836665592765070095594932211963293530758786715038170506783441806926060539983149082264884134111347541993170022903387584010789752125942119875134931628888282748259004262814537919998110869312084672945366050962018252662284796699425931413190067349368528463862282357874449024651587072321071636417118121963075739980137601265951824442005900211087003974196369569591120973714703115220993387701055123501187491187020293801542955586048885234554176713102913422119844337046623533028562349747780770756569091569485558858693026995131983783487912940835213749337805187285140052290094957269515165033080687052058942258714643488951196051662836924968618014274265747540386420087947131531835807390525331551708764821079556497213933540045594259186473803206967152652494058077275230017277319838467006568087931424429429676289538694939816381642268200452883835999582474245447417762981646620309733132766764448666626672337951736297947434392743078326450332226142150232072837176810325902779555133583722162588148884847992233371245481839405959499792299311603560545656609836413816429066413444547806572093798135981798600499769799701196159928183920533097285560670846824804536814785731353156306831236793698732857913643331208849113435638625362152883013168297132392157645612211505310995214349451696594977216916000402158524595225866569951453219135018738328541176593367245632724059458759759323289132199429435839730391890271462285579672812316728870530986894566894156185943484892757793544732454132452588740699305027546721202249408118663485240474960472091461353081820789562138681191683032261755771654403338590347130533748411302727028133159131459548282333054538039999666785061438849907538880444977742472059408761183293987064514928675748611099352453494323099987781245862925201657722098334927912653328487040242604120260573357433712976593640469409767471524043774163025730004240397177427981080359344526186930835789477305929364855955220115284254815869136596353983609618907146645363052871488164774443131351485557057992390275286192821687016272268769486209631072900706093164805764753538844810799818136250054261798735731411466639445702236628609775138226018377483821501779705232973742520072847303716060641885128644250263387417951655907173632802909132693240491679903036884586204139117674466308682089289779050093300437836181854910117260463963038811918177199832352406339324633858269130547008919397536926638129541811892961651937877617344955195525138798850643737181226576973496081506953647490264963408128594188175856494039293470645492143227029841906580949169841519178452267447739431778543885844207483285802070430518988770149415348385466312682666083272054747961890383847667529542926720943097421566873245493151819973445518749103134244421256565863813199163856281515998615877978939372087655879233837574477374482203580539315392702373103005932610512041171583948284072883696012703279724278196087723130663553483329815732757894069337974266526131531757827572118130420255662147178343282614941083823787088159475965914577221895762612873071571788095161773014165098941185616797741998413501362446481546131561734146250099353359608355349798047743828570938860712684696561387596135129057361234216223921665476177064704886973499603832655889813304997940552051779476601862950787855466985335242633331406814724900100559693970340518350965780928571958606477106234843660724683179696492319586159939178680044657259992352808452515405390965055350839414522417744941056314481286913900835303309436165451721642483386035052857216554658084637982241396887661409262954990748359136985876518389131365575325224553457277152911540978324104867957882117211344699990885479904690689209373818690125863333024505768627648277159947824746563639366079553084329777015720920001293961412959713513061285454532506623639503733540104726009368641255676779430075305510957666859023812578603295349023028618553749832119920226094055997377690296163291300803575045996441166806301502490450260656489250941844326130861876392462502884613118510014308714341419920580220488755977791245771686978621780403387279049316009315221282761396923062835402571774079871954531151266685756361190405786179863997344068152164745142524897730204092118143855405317944082521493422518317613074196462805648070013494883116882004797830412565696958279065952177095868847496615856875852827813700840223622561610205724003893286970820394311776709595607453373509304364840305069952253071508094565321578887063138658966575711049819432725968506965930299264055858177423532584243554764391610278179076245812181716331733159767873005927139753605775517120744004250432567177363584503824271363294656157510703027464952289280918078420433574244249786552393917572978712500322409413567808864770480362989064766191315200888400447492540383424696602021239736353891084877006003571681139812144518601466782766729076339952661466381190438945575188075171180135825803964011080368184144595766219179628343924571964117866881238351646791810054633514790090480044244685246024533808314928362155553765205438396723116142935075450090534837013734856677220282083148689064105138170868631895122129272060982997139875659986041345044350440927598486168740859881248566969923372060589951648114028836936704388949027171407618738222648780263600718103937678102460630405955327423976298361967379921490236772141189786313638175210409645244821740911631287628942078356239984976117168957007693658904438759589140649745855249646025304676914433806466179007002634722296651015289857094282501322900251659741108047304808503604808605953443391389201816835003736669323947661981562334664299378003823283506012908613626917253640755992580534561235403330513563433184311921752909314501366444647358186796261387016366273975550847865126346078704950794203263912243070102964503080187139456044715599312191926888336033853800136039906307961759929981034765131565665285357062755812508724646246576938803863584152146119129142215433310350605350043061109446660174055356688566632269360070882426362037823204020044131477637548964265797420406440203455139619314560448120115647321668061982480649019048385777227628441937345048054710943419343980811158314685075006484053366940174705907304079611684792646530235472006333076110574120487496348502866017575099422424941312865775622882350971868378969773121060297876975338019148889157716153492096851318552709076028059272548029438773875047381687939634495341685512643664231696478629048224472316041444252932601815776797792801595529986871529099021548381403098115162964634595550036775303387680861805861137545491529425401245054386393545831529415008237525623656592473044974441044445433588247192262911815940508229424374824427972571789678016455860632780682638159149431900407221261908828157935556386629092271527099527548495870693287431596032432813170791418070111288240997174197687045039388519282596515663904905899483642109930612002436419162932346974468120744933882539509389941962019047762216608957011722784055021500518051182386455695865138139265731364383557811531546972412222073847589808307671259289947493055201747562185914472471563537904639373432516604956957510953882072435930977225907249715370894200775843537944693315633809827093707371119887243789293950211589902345569778452807213111715048263369611842524703330048385057028466909305253336373281753304083288839157974079560719057087445555019809033629084808498482700958480836589924034313908129508178954403079678655369215555193487391832303113527535338604061475248064276862936758605367812980003425680369838450282475531576982183932638795992157158722571233321027011290298989159537809293240246808467427355220756060413176878244759327955244774312122618195057638789807285186306199600717614998210505569476805810678818980548760679753320874780578116884099700423716302102864814370267881993840332320606411659160486754107821615798064217137799684818996751279640380942073475112280910627589866684606623694380777240017114646807096674299884998468194716532630918779544419471882730607724108264936414916927895525116970379589815699860789428179752223540768603591111785116844998864190112486263849933610613465386927919192469831496598716697950848752582277438126636875521941759989636744054945416125552511322379108415541598503747293982471986260657665703465038601001235952116037944917901444627919809770467399267919231340786425321602602844904940428194927026211510168127986032737054183640162959410191530910128122872448951298789194912244209798914913155189119008412102279931826609234262961460122045725315785186425736461268034794021680658790786586247524764872803902837976103376819650464339061415489976640723044576837710810075626398219535580177406392400725774201348843029490585776329091934693098566888682178174163383443798637165141207014929599697879439430046777231331325642730394610854006632923911301838502897561606601450696228009791206968151401164151569201969226596586425189027828673870027190816633074193637388524012354109181117468059671715057145877044749894910112922449731993539660742656
であり、特に下 $1$ 桁は $6$ なので、$6$が答えとなります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。