寻找最小的幂，其首部由连续若干个相同数字构成

gxqcn

A132392 a(n) = smallest number k such that the decimal expansion of k^n begins with a string of at least n identical digits.

意思是说：搜索最小的 k，使 k^n 在10进制系统中的前 n 个数字为相同数字（相同数字数目可以大于 n）。 在上述链接中，给出了前100个值，见：Table of n, a(n) for n = 1..100 EXAMPLE 1^1 = 1, 15^2 = 225, 322^3 = 33386248, ... 现在的 任务是：设计一高效算法，可快速得到该类数； 目标是：继续补充该表，n → 128； 至于使用工具及第三方算法库等不作限制。

282842712474

要找到： 的整数解

mathe

这个不难. 直接对类似 111111 11111.1 1111.11 ... 222222 ... 等数据数值计算1/n次方,然后

gxqcn

我也有类似模糊的算法，再加上一些不等式方面的推导，看能否将效率发挥到极致。

无心人

哦，那上PARI/GP 最容易算了

gxqcn

刚刚抽空写了段代码，感觉算法已经比较高效了：

1. // 对应帖号： http://bbs.emath.ac.cn/viewthread.php?tid=1682&page=1&fromuid=8#pid20996
2. // 请复制并覆盖 HugeCalc 安装包解压后的 ansi_c++.cpp 文件；然后，编译、运行。。。
4. #include <iostream.h>
6. #include "../../../HugeCalc_API/CppAPI/Include/HugeCalc.h" // 公共接口
7. #include "../../../HugeCalc_API/CppAPI/Include/HugeInt.h" // 10进制系统
9. #pragma message( "automatic link to ../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
10. #pragma comment( lib, "../../../HugeCalc_API/CppAPI/Lib/HugeCalc.lib" )
12. void search( CHugeInt& hugeRoot, UINT32 r )
13. {
14. UINT32 i, k;
15. CHugeInt hugeSetp( (UINT32)1UL ), hugePow10( (UINT32)1UL );
16. CHugeInt hugeRadicand, hugeRem;
18. if ( r <= 1 )
19. {
20. hugeRoot = (UINT32)1UL;
21. return;
22. }
24. // k 可适当设定成较大的初值
25. ( hugeSetp.DecLShift( r ) /= 9 ) *= hugePow10.DecLShift( k = 0 );
27. cout << endl;
29. for ( ; ; )
30. {
31. for ( i=1, hugeRadicand=hugePow10; 10!=i; ++i )
32. {
33. hugeRoot.Root( hugeRadicand += hugeSetp, r, &hugeRem, NULL );
35. if ( !(!hugeRem) && hugeRem < hugePow10 )
36. {
37. ++hugeRoot.Root( hugeRadicand -= hugePow10, r, NULL, NULL );
38. return;
39. }
40. }
42. hugeSetp.DecLShift( 1 );
43. hugePow10.DecLShift( 1 );
45. if ( 0 == ( 63 & ++k ))
46. {
47. cout << "k = " << k << endl;
48. }
49. }
50. }
53. int main(int argc, char* argv[])
54. {
55. cout << "Call " << HugeCalc::GetVer() << endl;
57. if ( HC_LICENSE_NONE == HugeCalc::GetLicenseLevel())
58. {
59. cout << endl << "警告：您未通过 HugeCalc.dll 的许可认证！" \
60. << endl << endl << "解决方案可选下列方案之一：" \
61. << endl << " 一、请将本程序移动到“/CopyrightByGuoXianqiang/[../]”目录下运行；" \
62. << endl << " 二、或请在 HugeCalc.chm 中进行注册（一劳永逸）。" \
63. << endl << endl;
64. system( "pause" );
65. return (-1);
66. }
68. CHugeInt hugeInt;
69. UINT32 n;
71. #if 1 // 搜索指定的 a(n)
73. for ( ; ; )
74. {
75. cout << endl << "n = ";
76. cin >> n;
78. if ( 0 == n )
79. {
80. break;
81. }
83. // 初始化
84. HugeCalc::EnableTimer( TRUE );
85. HugeCalc::ResetTimer();
87. #else // 搜索连续的的 a(n)
89. // 初始化
90. HugeCalc::EnableTimer( TRUE );
91. HugeCalc::ResetTimer();
92. for ( n=1; n<=128; ++n )
93. {
95. #endif
97. search( hugeInt, n );
99. // HugeCalc::EnableTimer( FALSE );
101. cout << endl << HugeCalc::GetTimerStr( FT_HHMMSS_ms );
103. cout << "\tn = " << n << "\t" << hugeInt.GetStr( FS_NORMAL ) << endl;
104. }
106. system( "pause" );
108. return 0;
109. }

复制代码

gxqcn

经debug发现，HugeCalc 对 1111111111111111112000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 开19 次方长时间未返回结果， 需要进一步跟踪内部代码分析之。 上述问题发生在10进制内核系统，16进制系统正常。

gxqcn

5661458028330350155901213107326508707094693714908280127343664325554704200660811366009820667925779524 其 101 次方为： 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111272040234513006593936514036295273561213705494705918749286443667221120754808562488911189456902108535356194380905281481659750737794993958941317507899244498146987832345902699283785731604920509612682351798451388836237761441965529704914564363138189251254660739333842656090841550438817861994244469110321906927418510317101629243476995123859082446863883856700818224818383597504519502445702313305571121627020065654648177123771159362951641880148056880027409113104365916197501106850574459626856956809583098418623320006259563572236867240041412076232228676164162341247638657532583401148035267338587393558198570624809239724532084534303211012477524027938631666898992803028077307433396076763614226347838616495790109571297776954052357065952590373688005500251772486530214421506492392522189497591194763332875424115594380496874826169637901105459653289289599578652344173341159813491635378885921248371002615797985157539336793563610400049597795532765413668386179051902187775507409708215137788552822684478989150884407726252259057593636291323041356526541661843081183010803930525171608098603955839175464506732426853964082929246243987282566094620869168187183845058940517352660851170288126926105537881165913194482161155989792523077750199466217604245817107329307992049377502260723463351584763683291562286698676745336409280714763318327755328155616062467486451514012466119893520967054760735981394616111241964176122460951673531652115198106559912964025050231951315417666388855072323795335135693531511063856054118587055599579287358371133769986664979625225389987519160611642802125512662026106056227015077920590923608786721010271189568279905338383440986348558468600893365950107182945098942058534354506390288458366374935277559231755887195890609259332795353518440858590962502314132117422066009417634825799403265033934405245804718582418907994713618760279636221077168194705993940237078639402100085616995124020242754862487720959372541576939094891632856457507407208903097819549814871054462568394145318952011238372571794539018345882702682941498313806201781020672967841538531117500745415421114945916564828943197435335182701020001879574860570969596563842100350834833290373682866032437569698086583764217850332121576033485878923453491138856675592820998523462124684885810416969908680439883373508260044875826201234941703065255085047488409306636626111787044260230550848633726545528420951517790303971552334055893898731452957401973264045890664693320524895025992624189593593367508246202488597042949231057319968498342052144790985678988154577817864885963260268724611350022280105838375689564036496807489042646015344145878413704595917612406765872130383694061454653559905738213057910289020849166039292110227499269258207718964727651752927828557464039172684510827452882200950678514467191509431253376053809145459469160072675334336474004618363120713520687069766912353091387823404205690509381825493806804181357831959355839628884826675710924563936344128901691816257808467276234182353895470438786948571234454889566344530929821044441048303213257054370757554269064972941500149134459747169988818553128389813400352277742390023148185926368241590426893002406402558925821553572336376503896235286720080898627505509836368350095171885470944494600715323169754383533995531856640116125163779211213071667541331539272939728681332040498567812919514663892254803614324529476984072337295145312811177277024406514407192704678452274319114867722596062478489232082629784464916827899641598728761848113604763512666328901330966628301845663915144633057124540606755247819665815396132381698566514768130056606133478753651192586371371144703119303815620240875887398123905246523746268603930231644996593111604747847620321861386074089065083760557686590002658555674286614098144816162428077753217111018527414676127580248619677092412619968679964863888336350499106988341586465592022830545270692867946268998985018546968542987418107372487800133508248681947332141124238056585934983534041927565670735333001043355988088202780130763164848769256338561654791786329004534104909630767823086865340630210949364082793571904630838712529418294722328220276802983035812170030781354485898379912715758808171983148422054520857603265546205934180943072021779355749586444046969398758757636500366897195031647219931141705497478722137283331088086392705247412318849469749575643155418000396382979919549225868481964542874875008083005191249946719003107713084623699935210331808965979805803931357040308655459343954123587338749619520658721595088396495689175745211027299382450035027187126141014422872120819955167362801315313542551795575737912423842447175877660550086378122051201923820691772953391141942962132804497813847534528341365748987697053299926891580273355428087559472506655032601317599655200666139090300440806207876237673854678857452965306802674035503607141777626065490613100933943797991523421635419836090190223364539452691999903371863768750072170321977105704348978389247120173530619788000022950998847479818963657049293933975461070784673051275442601417525777222667621664771243987864890700136643624480577506694960532854217600116620742881870684038805602361371413021695110274917792164033347895600140013382772418932560551708610793672344424231380293740869533748128878907106181997007821845712633698448106427303091840442332162086708198968321003521459480615629331984696509723303158435196261087520729923332882657372938052735487874162635221332143262745613730288523133336302060203195610928050537188107472877976846564880732930755243683794396888595433971869997777930422360117945697322106867448199732144871481216235075656544182990390605484301668826042863329023312668791281560759876336595413569224828048231933970536325867219977073098520327452106458450582707321438530203860649430287459247768722242022922666305270077680229259655665234312577988985318232039803731852394470769445230177275447998488292643922535259627305627435882510184624525758005263749894047693591573310696735104243686843588056219383134293899865114267146993317124401651212524964995928975879430165314406362309571301245841806947973673361093933079664651595128145540564895453526446711388765653861551184900806602546177663784756973942818180626158002822520395021113904696825220767787073415527910641073109143762299203492010636199597567160153905699737758490217450346825124888998187416650139050517447021509694243968420289957188306517797526705972633446878133351706579409824895130435297404751871728100727572812347574039992333792561321100241710217437337776497457992910386570953623433815730941501883078000001741868200237278103214806891305819708132006509664628054349133104975712411464914839980261605403865108028524496227473190996255618663334163040330466465807802227242542531752552378671969437863254745506993256845081511019557350396600241510079981462467282111039516394668940661486407815518218201524288877133112813719683106766220316331261827577925427159726372879334089406137155908619662243797899338898708047749962593546947063494064218322890383500856292971394274029462231779691961354775928666333987062292713823544595053534467444874412505551705913944657433956219972286514365798520585007239153252630565082611350525195031431342684817659176071491731770099468240802571588083041070627097869452824048843650143839720512746118386576830632086033620240310829514750822866913881308236367986480241164268416720140122442687220575067919147395298310539418908110983688662402326531449373892454199037993502734842684460807702349557746120048190692049393013858999834322227250593261944737783871076304535414747131385501395008618326624938161980080946634062641700351977431998361476951942693469102561053744975660990249629399284379901672094158873129295211888429523551401339648453463260079418081420802412540198169629968118259424985360091778898264830969823620751598720652389642577493482997904540885186380008955652544500650413276988244692791891058014318414689752374603815375397901935074266165202189542171817730961193038401022550826281135595919539221487304150054275649394381484366674166398867305021931474721029185962659236586470727035407618599934207696516098096058556053174337689231902103267344544751813963923145428793531208317939074344152454505356484797662985854730860137391574844526194620139815805083351664835029462425910235058233963679310141839506884347979559581022840951609269996699669683584120135288706493739104051931545890286535754568384831614260995689148589285274719515350688404258859880556070343368178946205129355378262467642677750874160434787321015749837501706494642461609578736058613490236103478983425983597361985320777543852416346572157750201114018266662017162773545178720737124820545385200742261008232935075112317549012742809629734915853247784797121738734021328636799940134916924331752903058326293437735229938699066690000768783140679594911940905428500159023961258354408697398329971777232259032060970145539237347227146455167907606853744202810623366361899021584164285784785784594693750359075948029780236578871599766450552581017387970859899430468864050735303017831163957138249367979776258356209676604349905518042300191518111186096508123838517032397756644685553385751966812536292378350404227654079902762963782720150378838736247220634861036658746474319849490059861195062720303103050012915813105640319246002394437969441425765024026157052881423071309008402843392014475246510795021446718963941752245196085533188754090670435564126691621306387558270352494165747108362390205231592748628214245787977783839375504374314849385906014596522886365908496828261931068792905339474028453534707790823963059281320935086214572039894453900263663848202311349414531126380345917143498884127451145058676342745290350481611642010761838550032956721291091313729634482869852745946952851156294196857033493444561188654007620234710054674916663620569391823077299265409959591923227242388727273080672551997126120960199968984334368818117638767136123485365371213868435677907521159966893665597482304314328960318490375180579981014363450632668655135911208042676487222128466519941933732936162348303954062035188256684744405989196958480088786553853440707478573221634039936440698230130011220178731828806046872405658220472428621302636788310109033857024

gxqcn

38786795193301094194823540580919042198832156023736594084233149009772450628720654924033200169031509075 其 102 次方为： 1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111908494394882134842137094437678810381265980779566070180570988088422360533634803080668007836451308138783965756724509079529339853679073698842343026442706872058366819670424635873169441932007889889223253675406913446258647775962439913351398569442059348818750583922315122327039235947216972132321115385480391668059748098787802477602638976410413312635046216577939643469254599845128463144355534105949260143131182328460159826714282219712701003783651848030835518764217306807653998878044539858455846665105741971711512166580273272110891406832818388099487848594644812823931177721880197460330792400533402924994481676969492911856188135909590949435954505367032271507926778761731915653555751641946706700147637964251171860573848829668450430353843860849586528925847633420581210366973269431097716526810783497519997931997330104656984928649986372635284933899806884141223291587420415442495462949439921102488337000656039323450424533059381033604198207702412682631740989286679463965905322112521832241689187665057902576537043435124125176234889593531944346020272281452804671416506994981618333739860504379074654117925742218133566150173740447271205898001750865149945306582264605804108057967333208556886820387381249829756324825676708024406111597761889568996273372151961721663557199694648873326978221891200490810603814101154255220475015452747329786643781562706200066517960657417788105356726326028054695918623180142134004430652529903725262994330005358929361429633535495165663476742548219174418807196723941823134930533608728578912053159727053984867508940130415167662135890161763874478031297122736953558192355419601756977067878503630182105382701558267570966816309919167524436907226352932762848513283549531299715881412260380511625444463543175696222008182590664809901309650316849888355734512053503410420800156817853587948243565883985940021818186726662430280495643726455593779817057800331942842871645220169059655948273289806676286930592148107526593952974343419437614926948608777265402038594017642098278391206563773677805451314035547319252762728543037408439182026714442794773038121442386072467480082933452549595955983786750703906776035848570566848562437133141090797141570752144372359222377852511346203678976828891246697186296203581016535785281683728748003225451277038343003981201227546631542808096866847452888995360151933523422353553991144917794470133062922633376601707065338837461301114041897689221147092811204290260160241548287004390554660728199651348688665956735605518162246158437357972028946916865169033664378181102800877273236113963009126195143002862194025891042666188275046508807281543816135328615935649079891094014602212625363277069638646760599141032210869577189045414286402686821396159134227202803882592835240289772191820360526138575323505169460215184977991378029584822631069671900085354752321499335273464820836502969330642755332861995339744088411832694009290204574397331221470901235273281714636717326872962081313443924093186367726171382024191618723081586380993210897928953778629817348773359006406934995464807274087425632050207737166287358176733862146256131165828724553942468634963896477244182391519081489549446699734847550462621617389630383335338143719237491409226593088820717212145475811761640712682856379608205961379250708375973726092441829080790716085038184966782606078200132622004760707819944578423912088350425227014754580430954386927539184899647243888939394394009733858551963473206955325619528524233354644975664460663004156265642355641106097013953869683738001076346813284658668282568599989315945092979022951302300511316051070160900012242731393929838604133492039614116172497427132253874389868570564555532202799239268572843200559028995925800687614418538961231055870912556150546674046224717285531880621780369843772492403889627041234871441698645579012726727205486900072787945633221595829513151716479822859394107122259934593561388317140026954358779138506323271162332145751047723791908510760360779530611743582281761823540309019971743267507355373531475050686797862058162252321926946109996244973698760253817579388208911735900066775808831915994044384503705853973139243748291679629736175891679218041540533228827223887871024809074585867558147731225045590676104233289445590897291422564162725941592650154590101505370703318901555418932397749922413913474549025640763597226488901161482354605921833809503805979562526387378252989187865434882788846595547207982155125782624934007226157593193243935830131861969919680183520022153963535346034661423849672371641578961741822817028020065862204152418701199084354086439139742306672306614995374465242426353357214899242058785376632835993634481657860394043443772602070781040554228218959588536326099485857449503086190814556367324636184894273302902729317031905596137072162560944728101530140259439875272075233941852134844192025180037264449988168356164147412959225225725269384915558915196298444696276737487443880935965271801807064876410304793731134615900134915827879158478264908409756496356311728706501688302432382193754021525793128350433975967840870461720261472130257209580005000428440832307539694857581654923192018830442622979934413734753685488110222841854044431945608096748839633464036709574675493940632206615222791784670254348207852586850277308667608247838123805650993063014860814780591577996406055308316396565741622300350074113219307833409052123153506715644138270632612291209173933635819314618334209297160154580702198322342240388365244200243753047736997286171481891246986277427699464904457275418750993634646030408030835115847095065866172253682487264969527363118439608102083230885540787491688594199403018200141371879958519571939845588473983018784774451792211011917427031777075968089776468491466802689894805296579185133425752191386586152257606357743431764570449587271463236896780603221008510936761660421464912451288677376055336412137449306758419435707203850542538088071520809123078045160277738854913010245031117286246096580572728506352499348855812246144050202373915323913633649388389076003928766315163755274299409929226575206901546824532253982180617075926669242847092227275821843576829497246808897754527182142123491954490977228482410280303146932238540986121890302544178950619606105074025057558622674292072652968841128075151251600974992774644008894680050016443748764750031894374993185605639797746878509300104981167068231565142387106365302157615860942105406700417186434253541807576265385396451736475146566408100975242307776649917427944075338429453154964753714158149954519992796545586272249926792881084253562817907268041710207335407219427235075279340407469140446399740844411632278781591139205230263357619216202374061154514652184766034025699351636937117929951163244231056499745860102940635702208135862014492047168311004513060076617164273109122546942940787159578714146412239995920984284158903473018134419312869436883297706984210690622946444632021860608906975174533260702972135771200867598783320924786409550211212653845300584916623892353050398646686754773483800264574860553125001937697366090544027912129558779598847592298987744896588381095174379625744192449093457957615258278736764050857377705514683995920816363135282334197083668265401980949408765242536961522459902641221897146345575726321972536518613014562172474997775387027907396837269406951463906002755562910580099194815137184830564984854252439154555676153464547868992654437366669859898750158830250488721247968624857569130599191542710001681250757618544619529758963197328914828973491867620781855484104380729356481977008024916593242592216426096795577297843584020030012331630696076901838805598231877068547640834882469431564408015686209957121758869055512039337749221077322973266142924547038088041932467356256485594431356737687639213119179573485507790407218307766482157378479305456968070067493811490181973346445369670270268582796718318089051072620940748159107959311832196516378771337019801102454423665400022984132040639142638680978674122831751928549507899235906954280227126901331996214540410389690639795314185016420128985417740496732810381340244156999014851807992553269257796265501522728567782825019967356800250103883000002601380847127929285379530945012416737933718971923675904710246380942461615165574783505089016004793446633464717295405814544229713253642373266469596022589436217027677299697247476751117253304993829237572538526908011898400615196089588200903995828377103014245284015288761965797444770432552751692229960949075519097143761255015382910512017836684353386678361157682531954041459661355593607234870353904343921826964767613051510976050033240621778745013545140873421719800348133630172353139942120486746446540319883166661928237563728263148884501357152795578747714030338062443021742304536556150038082394869771005655664601856519994809460017076263994707027391892839674304241123203717326952003314569735019091870020332563327003582707504373181800083582787468724683630824535101267466524949882815842648570199637162838002226570554850590389103244455138707404071949284496137295237525184016549926482297858657485328346011845044727163444345880556008850785787144728205077298360928073432978240143546179281460987919475569039347600667256034909369903523855851804876635016973144756742318817157049623658014024262476148399330518619386888174337762087835442474992372511147093787146826367204122675411487769574123277770596650195031707687588126456259283242989635917787753512335898386311496906188881387715324325281595256233091106385765183597968559691734168030668208403002349933584658763427435666359216368657666981476593657197102120429234361230600010865717861349527198794193915615726670469034412531232073148146983484791222099483569335375147415824239116418174708447815294136604796593224274717108797275340768182369603822640794553575276759593826460040911129155719484542517244683721002957462349842824855819447673322882745806671841629540326789139586193092838049598047325998006085795325570835571766936401764355800705316510215167879292692385677972673431086438177367453830800580405392877133063337404576226056339222879129108919762425966648895477974566464560237846732469090257397978431486953803690482568446521077650823709887930258407503132402059600059693501164092693695309948970789123127737760053498593430585796970356075744594841246366744128565549693545124980780702894086305670878924088596189005253918673205539287642852619431010907646850682795047760009765625

gxqcn

605028066914946672922284793621475597550918291182272747957529407945663306180863738253311978623958446423 其 103 次方为： 33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333334746408392976304959748199148489569516054182873729292344825273904142314431947774817937531930183975188422574788978629537249684749803822059711239955151705190431108613192887835987075633737078160536854224198230097164941333869324235796092537167384984551276490446145835455807870486134332894896738898393105908579140171332075194190045333154031307056483335932696557852286009674514918599027438292316328769414333335420535852425397100766984221370341977187063884687064625436517441822370998316161004975582627892360530408653129803586299689120412798711591710695235125088038266184413865413500288871437605157596663004279686972792110516924896499329915621126139916655153536124780505984274315703076283232932488320022249919911206068307486862821466139571386667615128838273169169112904139238714766275399354844928883476241327974190416460554248953380032584857244085326546080741062753215489206773041659501984158815238767886904467789576469843990997800453052685013545926125830195476214532941165311997518928152189534019445593161880869950279467276033517523798189877362223616210999819683895570900505421435561582433719104774452094454688598342642981446563496310641369407744415419099081220457248626083446246965284194724883353836066513077664365306075777063864861802301783921854786547159609242740305937439992189006251331016218830563115119985598345331148514142949811831437069538560906450784775498609229893198814698082444855863777587244781909763090699299705880521196696108150808685389357504972363339761205301795479680595421913477382264099083366917416080930257466197771826796047286432848858868165598777897651891690191114391502199109216305720357577492703809770448391062445505963702436237463831117187209066202664041795603765985576643462912650309807471773725718227706297986025804793260429072875046652234550225892829538838162695489235322968755395471581653644220399909862310375536210350778738315858175611777995953571982896039474742801935199890958723334656677470712286546887006418356189175091390285918454403294364857300053039468901315120441691642892703939825217951615338776855065739654394908696674224434256327025734586699928289356121875301177313666445463442165404470453557985845073868291760133121953662050990200788398684570788396795319761835550629036574412190471378353312643458819057854231906121554815580775366674845356517300670817860480670067246052794217134862234443611597360568063636126324685859189341687021294762244649736574299868565287830012059242510448671945161383772025104371356473945929351256299501028755633120235034563399831633474618576125851657855322560482611214076785921450472060717536104728111335948613673124411643318552557802167160941449055961717816694231310926223296816014824256685760842733899966298229031944349340824608990724442965301234488549038640524087601693083882114262506862909771697868509786742489027419360605481191994570836588871145493367907225005186777319102271735383380454130287585493686723230105423499179201135526713728426558021912751708565502193858557731619670907171802153995035660941126080082357005009908543116946177155989564522100648894569871025723837046569468333888350984511833114516196909249102961505162619193146942512778878883217616470628772286355612511887003233740452528069014621753884416553775865506450376304181474230050746963908843395502996176781324274149989928620423874435165928629906945181243085125463432089900749480782158746045824485956195014746503513814913641333251062158003906265497183152107812905016075198397150842623622577910833045213297709180500107862290690118859168623600241210677605745463258203844459969070348868342463015898641150823285856499921190283195732999884122884930928453734624028035904076517175752977275519685131722605211220879583115612912742522795364580213957011911546688753391341600961579994055888061467968503085829532548660355482755981863529193866113006859653640065493244975664411733108063581344852813699274681163207167338757314251315709466488628127830848599740428775077245997907672067244584081328712316164957718110409125965839903671241259769383560513544514505364839604326302674833467760824731004314782862402312226166701277554377547827847561989844768042160933902685236431236300467354634453246623802241224440564655380289825394750991661821043868811164646918523596885417324088300381231411242419227388540672442747254410592307163353766724276139236829152883150481366827782539146078563063922605961749294258643549979001218987589147487491999512351834700548857948079555539811025190293033434157379292450069678740478301447248361473863272613295459148216429704337567005300284013592332896058240212356864346668335988288644650177548043767131451016072803613655452395236702864604784960302833165312434230705381476906315036393903914780011902844033592189529125527981163624583417716606333159801374218323084793000187697750845739318526114235118626747917999897352417781633559522124066680342759714393703448393532957665099114055560550079179395408611686715403773928620811826829922712279645257187947840203829364721076876054113927073134129600436379403378269158680859995643819269326562042459963621298885713144176631764929952020060696342079188811287756731900336339272878229426759214154838740302623066534480015297805362001507011076456395666000113734947343739354033973376080248503460251264113442637074295007896632892147754154581381461427809102293124364270581592700311917097144520501407221413927408869538407238473271121509467476188473933147156150591595482150930302024071953654167091857458253647477509399539679300383751973825655131785599694968669927503308299457171192111336273690988471865029365340473506049049875948215931270125827309586348690858694358675529219629878115147401937260748661421061755354481306358831121269039063316140015201693762029496177879230679766889904149416121833577754478514048479429621163472977090736342242233018898063722903429201202987991167975143812188157589715361502859840037328584418802478837417773590166812750831930178238161085834625195123221598585541799161804705447771769121246175396039971006819672767913773039948247698276007038220711831807308148481310509492305044940272113704380429574549024904693038944869161980429234256717412408820707712307419749749389090393019158826147368378615825405416167923398302040751363558578243375445702531520535217238080256977672555621593442119223547945081024741077821273679413614553961310083393562108019753329863802068218013387084061487450648504451663775896677733378564155640711779802827773297890756942539684880794463025334714476508538804191707332910898716787127579711564298120382629478383281496873491718818827127637668202142060302773406515115283646985053623327742382331247555582432627954899107493740492204994333112552406884486644145110610087627799656447349411509484349904235636410529265156735155273852208271713394366486023428186333237849121387285260136281442696412816873146190147002105165114458725398110977063242177814383296047625275891623950823831049603201415011898943852107700447799660945047681744354318474900065902757577939104734123470250305965935354017974119153136175405684414462440769826862840302143278173159955288555689369664780832379162758638440392395563238051152656336062758984303431190107574815696484800927991315476601364913920111248354736756626291846733075661170734257726043041067657508285017631889857856434202189188687064395894302486518970526134984751433326571475479920887306586967276483309331596220050533606136728433663895395570050585786760231017625723109442271941077131602433369880560199267438541879544048136076548050395587723903064326202715182650299282935995387455305642339855233708799379964167256239343162466671631463450967703865984354490060737448079311704761804783814560532008059088091258255614212984200499387857650833963694800603438738104643390918610787878564962828819779321161954740569478000030734378965289996347812256848791944756481994409098455105677218914929054770497805700283300812603080005952200021730022393471581216076746701503102713754023435101319215878798220023018618312321411612342956473566457548082315871902390663095208633031178771020260320379035326658401220957088959706438313524134647904050091486485477029716902563181319638100592606305391911910743566621382826812417003554097329617712217561715996658685616738649256861700618620751001136331142339586514706432257341480397311972753600619660242067864941164567584635994031134134340173551044467802132222658075120248189380377294578989891660819231269120186190908420855709027134332121854402340407288423308781821351870514162458379681332225568472958304497638320714605789355359789701344411504795353099134517826007741870224900630173946107773325949379221285752970581676432697950841690963691981690011853874831830916878251751674921620613623790209384532525115752069199036063448492307895714788596573112643817088197736532670030184295892641341980820737997172389714932286618667728866202635005309234708549710140203816132536273385059422995888086526254553637648689286045692017122891660654151567660121587235370088610536886070268011159929858463679524533817472351075652051962407035414615605275228591158407403509483484685737006994432577357377340888497419585793934213071646597735567535009185251958953902755787087599433433299730264550941473315376198296731667558302523027741005190288890408615939823868062769800577844562568421101278477156279528175144075043931061195550058079679457933133204136466670065976795705361069226389744355619736166714055407219265138717308635163531903907872464414455386283905197010505821457986569503903123938221348206480308033134493170469962402438682426114987135251319685726441579228921400969216168214006129394028848622246657951644721509914833805237673558677610105444464705157882780330233010916502552891464497385330335842670225509089441978063623357368416086880830318063244961735740597488423531302562659566017735767205587998659061508190998101879325679338218026101269899345631877400296997466644640722455448142446675058024046759853110836011747170066699377838423637559623373223753651301538141407176281662971683021124326849110767016726521241778062998143140234183082597302695365447795296751688012412205873546599760495390159855929036042970982595522333126513969624277130690657581038196114486163760070397684242003724037259641771137133728258342212377172332651860235216999577593543399306935270320295790582253246640015432266071961394644069177480297194725672490202762348827563936388966429493523732011823987158896130435164105112809371367391721592553736911923759161134598170267298070981523084258827168277427268730572335954408315660021986427624339698593129897023240106976895836512704928223782701192605340967