순환소수 중에서 가장 긴 자리수는? (프로젝트 오일러 #26)

언뜻 보기엔 평범한 문제로 생각하기 쉽다.

그냥 long double에다 대입한 뒤에 결과를 문자열 형식으로 출력해서 문자열을 비교하면 될 것 같은 생각착각이 든다.

그런데, 이 바닥 문제 중에 그런 만만한 건 없다.

이 문제의 요지는 아무리 긴 숫자도 일일이 나누어 저장하여, 순환 여부를 정확히 비교할 수 있는 코드를 만드는 것이다.

순환 여부를 확인하려면 숫자를 나누면서 각 자리의 몫과 그 때의 나머지를 모두 저장하고 이를 모두 비교해야 한다.

아래의 divide() 함수가 이 기능을 수행하는 함수다.

quotient[]에는 각 자리의 몫을, remain[]에는 해당 자리의 나머지를 저장한다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// a / b
int divide(unsigned a, unsigned b, string &ret)
{
    ret.clear();

    if (!b) return 0;
    unsigned quot_ = a / b;
    a %= b;

    vector<unsigned> quotient;
    vector<unsigned> remain;

    while (a) {
        a *= 10;
        if (a < b) {
            quotient.push_back(0);
            remain.push_back(a);
        }
        else {
            quotient.push_back(a / b);
            a %= b;
            remain.push_back(a);
        }

        if (quotient.size()>1) {
            int len = quotient.size();
            for (int i = len - 2; i >= 0; i--) {
                if ((quotient[len - 1] == quotient[i]) && (remain[len - 1] == remain[i])) {
                    // i ~ len-2 이 반복임

                    ret = to_string(quot_) + '.';

                    for (int j = 0; j < i; j++) {
                        ret.push_back((char)('0' + quotient[j]));
                    }

                    ret.push_back('(');

                    for (int j = i; j < len - 1; j++) {
                        ret.push_back((char)('0' + quotient[j]));
                    }

                    ret.push_back(')');

                    return len - 1 - i;
                }
            }
        }
    }

    return 0;
}

int main(int argc, char* argv[])
{
    int maxdigits = 0;

    for (unsigned i = 1; i < 1000; i++) {
        string repetation;
        int len = divide(1, i, repetation);
        if (len > maxdigits) {
            cout << i << " : " << repetation << " [" << len << "]" << endl;
            maxdigits = len;

        }
    }

    return 0;
}

이렇게 계산된 결과의 일부는 아래와 같다.
답은 983으로, 무려 982자리의 순환소수가 나온다.

863 : 0.(0011587485515643105446118192352259559675550405561993047508690614136732329084588644264194669756662804171494785631517960602549246813441483198146002317497103128621089223638470451911935110081112398609501738122827346465816917728852838933951332560834298957126303592120509849362688296639629200463499420625724217844727694090382387022016222479721900347624565469293163383545770567786790266512166859791425260718424101969872537659327925840092699884125144843568945538818076477404403244495944380069524913093858632676709154113557358053302433371958285052143684820393974507531865585168018539976825028968713789107763615295480880648899188876013904982618771726535341830822711471610660486674391657010428736964078794901506373117033603707995365005793742757821552723059096176129779837775202780996523754345307068366164542294322132097334878331402085747392815758980301274623406720741599073) [862]
887 : 0.(0011273957158962795941375422773393461104847801578354002254791431792559188275084554678692220969560315670800450958286358511837655016910935738444193912063134160090191657271702367531003382187147688838782412626832018038331454340473506200676437429537767756482525366403607666290868094701240135287485907553551296505073280721533258173618940248027057497181510710259301014656144306651634723788049605411499436302142051860202931228861330326944757609921082299887260428410372040586245772266065388951521984216459977452085682074408117249154453213077790304396843291995490417136414881623449830890642615558060879368658399098083427282976324689966178128523111612175873731679819616685456595264937993235625704622322435174746335963923337091319052987598647125140924464487034949267192784667418263810597519729425028184892897406989853438556933483652762119503945885005636978579481397970687711386696730552423900789177) [886]
937 : 0.(001067235859124866595517609391675560298826040554962646744930629669156883671291355389541088580576307363927427961579509071504802561366061899679829242262540021344717182497331910352187833511205976520811099252934898612593383137673425827107790821771611526147278548559231590181430096051227321237993596584845250800426894343649946638207043756670224119530416221985058697972251867662753468516542155816435432230522945570971184631803628601921024546424759871931696905016008537886872998932764140875133404482390608324439701173959445037353255069370330843116328708644610458911419423692636072572038420490928495197438633938100320170757737459978655282817502668089647812166488794023479188900747065101387406616862326574172892209178228388473852721451440768409818569903948772678762006403415154749199573105656350053361792956243329775880469583778014941302027748132337246531483457844183564567769477054429028815368196371398078975453575240128068303094983991462113127) [936]
941 : 0.(0010626992561105207226354941551540913921360255047821466524973432518597236981934112646121147715196599362380446333687566418703506907545164718384697130712008501594048884165781083953241232731137088204038257173219978746014877789585547290116896918172157279489904357066950053134962805526036131774707757704569606801275239107332624867162592986184909670563230605738575982996811902231668437832093517534537725823591923485653560042507970244420828905419766206163655685441020191285866099893730074388947927736450584484590860786397449521785334750265674814027630180658873538788522848034006376195536663124335812964930924548352816153028692879914984059511158342189160467587672688629117959617428267800212539851222104144527098831030818278427205100956429330499468650371944739638682252922422954303931987247608926673751328374070138150903294367693942614240170031880977683315621679064824654622741764080765143464399574920297555791710945802337938363443145589798087141339) [940]
953 : 0.(0010493179433368310598111227701993704092339979013641133263378803777544596012591815320041972717733473242392444910807974816369359916054564533053515215110178384050367261280167890870933892969569779643231899265477439664218258132214060860440713536201469045120671563483735571878279118572927597061909758656873032528856243441762854144805876180482686253934942287513116474291710388247639034627492130115424973767051416579223504721930745015739769150052465897166841552990556138509968520461699895068205666316894018887722980062959076600209863588667366211962224554039874081846799580272822665267576075550891920251836306400839454354669464847848898216159496327387198321091290661070304302203567681007345225603357817418677859391395592864637985309548793284365162644281217208814270724029380902413431269674711437565582371458551941238195173137460650577124868835257082896117523609653725078698845750262329485834207764952780692549842602308499475341028331584470094438614900314795383) [952]
971 : 0.(0010298661174047373841400617919670442842430484037075180226570545829042224510813594232749742533470648815653964984552008238928939237899073120494335736354273944387229660144181256436663233779608650875386199794026776519052523171987641606591143151390319258496395468589083419155509783728115345005149330587023686920700308959835221421215242018537590113285272914521112255406797116374871266735324407826982492276004119464469618949536560247167868177136972193614830072090628218331616889804325437693099897013388259526261585993820803295571575695159629248197734294541709577754891864057672502574665293511843460350154479917610710607621009268795056642636457260556127703398558187435633367662203913491246138002059732234809474768280123583934088568486096807415036045314109165808444902162718846549948506694129763130792996910401647785787847579814624098867147270854788877445932028836251287332646755921730175077239958805355303810504634397528321318228630278063851699279093717816683831101956745623069) [970]
977 : 0.(0010235414534288638689866939611054247697031729785056294779938587512794268167860798362333674513817809621289662231320368474923234390992835209825997952917093142272262026612077789150460593654042988741044012282497441146366427840327533265097236438075742067553735926305015353121801432958034800409416581371545547594677584442169907881269191402251791197543500511770726714431934493346980552712384851586489252814738996929375639713408393039918116683725690890481064483111566018423746161719549641760491299897645854657113613101330603889457523029682702149437052200614124872057318321392016376663254861821903787103377686796315250767656090071647901740020470829068577277379733879222108495394063459570112589559877175025588536335721596724667349027635619242579324462640736949846468781985670419651995905834186284544524053224155578300921187308085977482088024564994882292732855680655066530194472876151484135107471852610030706243602865916069600818833162743091095189355168884339815762538382804503582395087) [976]
983 : 0.(0010172939979654120040691759918616480162767039674465920651068158697863682604272634791454730417090539165818921668362156663275686673448626653102746693794506612410986775178026449643947100712105798575788402848423194303153611393692777212614445574771108850457782299084435401831129196337741607324516785350966429298067141403865717192268565615462868769074262461851475076297049847405900305188199389623601220752797558494404883011190233977619532044760935910478128179043743641912512716174974567650050864699898270600203458799593082400813835198372329603255340793489318413021363173957273652085452695829094608341810783316378433367243133265513733468972533062054933875890132248219735503560528992878942014242115971515768056968463886063072227873855544252288911495422177009155645981688708036622583926754832146490335707019328585961342828077314343845371312309257375381485249237029501525940996948118006103763987792472024415055951169888097660223804679552390640895218718209562563580874872838250254323499491353) [982]

덧1. 이 코드는 벡터를 사용했는데, 정적배열로 구현한 것에 비해 다소 느리다. 굳이 벡터를 사용할 필요는 없는 것 같다.

덧2. string을 사용한 부분도 비슷한 생각임. 초기 버전은 char[]에 저장했는데, 이 편이 더 합리적인 접근인 듯.