【EOJ】2895循环小数

r囧r小猫 2022-06-13 12:57 246阅读 0赞

这题主要是难在边界处理，有的情况想不到，我自己这个代码，改到后来，我自己都蒙圈了，看来还是加强代码风格。不过我很喜欢用数组模拟hashmap，也是以前用pascal留下的毛病，哎~~ 上代码

#include<iostream>
    using namespace std;
    int main(){
    	int a,b,yushu,d[10000],d1[10000],d2[100001],i,tail,head;
    	char c;
    	bool a1[100001],b1[10],swi;
    	while(cin>>a){
    		c=getchar();
    		cin>>b;
    		for(i=0;i<100001;i++){
    			a1[i]=false;
    			d2[i]=-1;
    		}
    		yushu=a%b;
    		i=0;
    		swi=false;
    		head=1;
    		while(yushu!=0){
    			d[i]=yushu*10/b;
    			if(a1[yushu]==true&&yushu==d1[d2[yushu]]){
    				tail=i;
    				d1[i]=yushu;
    				break;
    			}
    			if(a1[yushu]==false){
    				a1[yushu]=true;
    				d2[yushu]=i;
    			}
    			i++;
    			d1[i-1]=yushu;
    			yushu=yushu*10%b;
    		}
    		if(yushu==0)
    			cout<<'0'<<endl;
    		else{
    			for(i=tail;i>0;i--)
    				if(d[i-1]==d[tail]&&d1[i-1]==d1[tail]){
    					head=i;
    					break;
    				}
    			for(i=head-1;i<tail;i++)
    				cout<<d[i];
    			cout<<endl;
    		}
    	}
    }

附几组循环节较长的分数：  
数据转自：http://hi.baidu.com/zgmg/blog/item/62cef7a239287eb6caefd015.html  
96÷97的循环节共96位，为：989690721649484536082474226804123711340206185567010309278350515463917525773195876288659793814432  
108÷109的循环节共108位，为：990825688073394495412844036697247706422018348623853211009174311926605504587155963302752293577981651376146788  
112÷113的循环节共112位，为：9911504424778761061946902654867256637168141592920353982300884955752212389380530973451327433628318584070796460176  
130÷131的循环节共130位，为：9923664122137404580152671755725190839694656488549618320610687022900763358778625954198473282442748091603053435114503816793893129770  
148÷149的循环节共148位，为：9932885906040268456375838926174496644295302013422818791946308724832214765100671140939597315436241610738255033557046979865771812080536912751677852348  
166÷167的循环节共166位，为：9940119760479041916167664670658682634730538922155688622754491017964071856287425149700598802395209580838323353293413173652694610778443113772455089820359281437125748502  
178÷179的循环节共178位，为：9944134078212290502793296089385474860335195530726256983240223463687150837988826815642458100558659217877094972067039106145251396648044692737430167597765363128491620111731843575418  
180÷181的循环节共180位，为：994475138121546961325966850828729281767955801104972375690607734806629834254143646408839779005524861878453038674033149171270718232044198895027624309392265193370165745856353591160220  
192÷193的循环节共192位，为：994818652849740932642487046632124352331606217616580310880829015544041450777202072538860103626943005181347150259067357512953367875647668393782383419689119170984455958549222797927461139896373056  
222÷223的循环节共222位，为：995515695067264573991031390134529147982062780269058295964125560538116591928251121076233183856502242152466367713004484304932735426008968609865470852017937219730941704035874439461883408071748878923766816143497757847533632286  
256÷257的循环节共256位，为：9961089494163424124513618677042801556420233463035019455252918287937743190661478599221789883268482490272373540856031128404669260700389105058365758754863813229571984435797665369649805447470817120622568093385214007782101167315175097276264591439688715953307392  
312÷313的循环节共312位，为：996805111821086261980830670926517571884984025559105431309904153354632587859424920127795527156549520766773162939297124600638977635782747603833865814696485623003194888178913738019169329073482428115015974440894568690095846645367412140575079872204472843450479233226837060702875399361022364217252396166134185303514376  
418÷419的循环节共418位，为：9976133651551312649164677804295942720763723150357995226730310262529832935560859188544152744630071599045346062052505966587112171837708830548926014319809069212410501193317422434367541766109785202863961813842482100238663484486873508353221957040572792362768496420047732696897374701670644391408114558472553699284009546539379474940334128878281622911694510739856801909307875894988066825775656324582338902147971360381861575178  
502÷503的循环节共502位，为：9980119284294234592445328031809145129224652087475149105367793240556660039761431411530815109343936381709741550695825049701789264413518886679920477137176938369781312127236580516898608349900596421471172962226640159045725646123260437375745526838966202783300198807157057654075546719681908548707753479125248508946322067594433399602385685884691848906560636182902584493041749502982107355864811133200795228628230616302186878727634194831013916500994035785288270377733598409542743538767395626242544731610337972166  
618÷619的循环节共618位，为：998384491114701130856219709208400646203554119547657512116316639741518578352180936995153473344103392568659127625201938610662358642972536348949919224555735056542810985460420032310177705977382875605815831987075928917609046849757673667205169628432956381260096930533117932148626817447495961227786752827140549273021001615508885298869143780290791599353796445880452342487883683360258481421647819063004846526655896607431340872374798061389337641357027463651050080775444264943457189014539579967689822294022617124394184168012924071082390953150242326332794830371567043618739903069466882067851373182552504038772213247172859450726978  
700÷701的循环节共700位，为：9985734664764621968616262482168330955777460770328102710413694721825962910128388017118402282453637660485021398002853067047075606276747503566333808844507845934379457917261055634807417974322396576319543509272467902995720399429386590584878744650499286733238231098430813124108416547788873038516405135520684736091298145506419400855920114122681883024251069900142653352353780313837375178316690442225392296718972895863052781740370898716119828815977175463623395149786019971469329529243937232524964336661911554921540656205420827389443651925820256776034236804564907275320970042796005706134094151212553495007132667617689015691868758915834522111269614835948644793152639087018544935805991440798858773181169757489300  
810÷811的循环节共810位，为：998766954377311960542540073982737361282367447595561035758323057953144266337854500616522811344019728729963008631319358816276202219482120838471023427866831072749691738594327990135635018495684340320591861898890258939580764488286066584463625154130702836004932182490752157829839704069050554870530209617755856966707768187422934648581997533908754623921085080147965474722564734895191122071516646115906288532675709001233045622688039457459926017262638717632552404438964241676942046855733662145499383477188655980271270036991368680641183723797780517879161528976572133168927250308261405672009864364981504315659679408138101109741060419235511713933415536374845869297163995067817509247842170160295930949445129469790382244143033292231812577065351418002466091245376078914919852034525277435265104808877928483353884093711467324290  
936÷937的循环节共936位，为：998932764140875133404482390608324439701173959445037353255069370330843116328708644610458911419423692636072572038420490928495197438633938100320170757737459978655282817502668089647812166488794023479188900747065101387406616862326574172892209178228388473852721451440768409818569903948772678762006403415154749199573105656350053361792956243329775880469583778014941302027748132337246531483457844183564567769477054429028815368196371398078975453575240128068303094983991462113127001067235859124866595517609391675560298826040554962646744930629669156883671291355389541088580576307363927427961579509071504802561366061899679829242262540021344717182497331910352187833511205976520811099252934898612593383137673425827107790821771611526147278548559231590181430096051227321237993596584845250800426894343649946638207043756670224119530416221985058697972251867662753468516542155816435432230522945570971184631803628601921024546424759871931696905016008537886872  
1018÷1019的循环节共1018位，为：9990186457311089303238469087340529931305201177625122669283611383709519136408243375858684985279685966633954857703631010794896957801766437684003925417075564278704612365063788027477919528949950932286555446516192345436702649656526005888125613346418056918547595682041216879293424926398429833169774288518155053974484789008832188420019627085377821393523061825318940137389597644749754661432777232580961727183513248282630029440628066732090284592737978410206084396467124631992149165848871442590775269872423945044160942100098135426889106967615309126594700686947988223748773307163886162904808635917566241413150147203140333660451422963689892051030421982335623159960745829244357212953876349362119725220804710500490677134445534838076545632973503434739941118743866535819430814524043179587831207065750736015701668302257114818449460255152109911678115799803729146221786064769381746810598626104023552502453385672227674190382728164867517173699705593719332679097154072620215897939156035328753680078508341511285574092247301275760549558390578  
2296÷2297的循环节共2296位，为：9995646495428820200261210274270787984327383543752720940356987374836743578580757509795385285154549412276882890727035263387026556377884196778406617326948193295602960383108402263822377013495864170657379190248149760557248585111014366565084893339138006094906399651719634305616020896821941663038746190683500217675228558989986939486286460600783630822812363952982150631258162821070962124510230735742272529386155855463648236830648672181105790161079669133652590335219851980844579886808881149325206791467131040487592511972137570744449281671745755333043099695254680017414018284719198955158902916848062690465824989116238572050500653025685676969960818458859381802350892468437091858946451893774488463212886373530692207226817588158467566390944710491946016543317370483239007400957771005659555942533739660426643447975620374401393121462777535916412712233347845015237265999129299085764040052242054854157596865476708750544188071397474967348715716151501959077057030909882455376578145407052677405311275576839355681323465389638659120592076621680452764475402699172834131475838049629952111449717022202873313016978667827601218981279930343926861123204179364388332607749238136700043535045711797997387897257292120156726164562472790596430126251632564214192424902046147148454505877231171092729647366129734436221158032215933826730518067043970396168915977361776229865041358293426208097518502394427514148889856334349151066608619939050936003482803656943839791031780583369612538093164997823247714410100130605137135393992163691771876360470178493687418371789290378754897692642577274706138441445363517631693513278188942098389203308663474096647801480191554201131911188506747932085328689595124074880278624292555507183282542446669569003047453199825859817152808010448410970831519373095341750108837614279494993469743143230300391815411406181976491075315629081410535481062255115367871136264693077927731824118415324336090552895080539834566826295167609925990422289943404440574662603395733565520243796255986068785372224640835872877666521549847627340008707009142359599477579451458424031345232912494558119286025250326512842838484980409229429690901175446234218545929473225946887244231606443186765346103613408794079233783195472355245973008271658685241619503700478885502829777971266869830213321723987810187200696560731388767958206356116673922507618632  
2970÷2971的循环节共2970位，为：999663412992258498821945472904745876809155166610568832043083136990912150790979468192527768428138673847189498485358465163244698754628071356445641198249747559744193874116459104678559407606866374957926624032312352743184113093234601144395826321104005385392123864018848872433524065971053517334230898687310669808145405587344328508919555705149781218444968024234264557388084819925950858296869740828004039044092898014136654325143049478290138000673174015483002356109054190508246381689666778862335913833726018175698418041063614944463143722652305621003029283069673510602490743857287108717603500504880511612251767081790642881184786267250084146751935375294513631773813530797711208347357791989229215752271962302255132951868057892965331538202625378660383709188825311342982160888589700437563110063951531470885223830360148098283406260518343991921911814203971726691349713901043419723998653651969033995287781891618983507236620666442275328172332547963648603163917872770111073712554695388757993941433860652978795018512285425782564792998990238976775496465836418714237630427465499831706496129249410972736452372938404577583305284416021541568495456075395489734096263884214069336923594749242679232581622349377314035678222820599124873779872096937058229552339279703803433187478963312016156176371592056546617300572197913160552002692696061932009424436216762032985526758667115449343655334904072702793672164254459777852574890609222484012117132278694042409962975429148434870414002019522046449007068327162571524739145069000336587007741501178054527095254123190844833389431167956916863009087849209020531807472231571861326152810501514641534836755301245371928643554358801750252440255806125883540895321440592393133625042073375967687647256815886906765398855604173678895994614607876135981151127566475934028946482665769101312689330191854594412655671491080444294850218781555031975765735442611915180074049141703130259171995960955907101985863345674856950521709861999326825984516997643890945809491753618310333221137664086166273981824301581958936385055536856277347694378996970716930326489397509256142712891282396499495119488387748232918209357118815213732749915853248064624705486368226186469202288791652642208010770784247728037697744867048131942107034668461797374621339616290811174688657017839111410299562436889936048468529114776169639851901716593739481656008078088185796028273308650286098956580276001346348030966004712218108381016492763379333557724671827667452036351396836082127229888926287445304611242006058566139347021204981487714574217435207001009761023224503534163581285762369572534500168293503870750589027263547627061595422416694715583978458431504543924604510265903736115785930663076405250757320767418377650622685964321777179400875126220127903062941770447660720296196566812521036687983843823628407943453382699427802086839447997307303938067990575563783237967014473241332884550656344665095927297206327835745540222147425109390777515987882867721305957590037024570851565129585997980477953550992931672837428475260854930