Project Euler Problem 64 (C++代码)

Problem 64 : Odd period square roots

All square roots are periodic when written as continued fractions and can be written in the form:

It can be seen that the sequence is repeating. For conciseness, we use the notation √23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

√2=[1;(2)], period=1
√3=[1;(1,2)], period=2
√5=[2;(4)], period=1
√6=[2;(2,4)], period=2
√7=[2;(1,1,1,4)], period=4
√8=[2;(1,4)], period=2
√10=[3;(6)], period=1
√11=[3;(3,6)], period=2
√12= [3;(2,6)], period=2
√13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 10000 have an odd period?

C++代码

#include <iostream>
#include <vector>
#include <iterator>
#include <cmath>
#include <cassert>

using namespace std;

//#define UNIT_TEST

class PE0064
{
private:
    int getPeriod(int N);

public:
    int getNumOfContinuedFractions(int maxN);
};

int PE0064::getPeriod(int N)
{
#ifdef UNIT_TEST
    vector<int>fractions_vec;
#endif
    int period = 0;
    int m = 0, d = 1;
    double root = sqrt((double)N);
    int a0 = int(root);
    int a = a0;

#ifdef UNIT_TEST
    fractions_vec.push_back(a0);
    // cout << "m=" << m << ", d=" << d << ", a=" << a << endl;
#endif

    while (a != 2*a0)
    {
        m = a*d - m;
        d = (N - m*m) / d;
        a = int((root + m) / d);
        period++;

#ifdef UNIT_TEST
        fractions_vec.push_back(a);
        //cout << "m=" << m << ", d=" << d << ", a=" << a << endl;
#endif
    }

#ifdef UNIT_TEST
    cout << "√" << N << " = [" << fractions_vec[0] << "; (" ;
    copy(fractions_vec.begin()+1, fractions_vec.end()-1, 
         ostream_iterator<int>(cout, ","));
    int size = fractions_vec.size();
    cout << fractions_vec[size-1] << ")], period = " << period << endl;
#endif

    return period;
}

int PE0064::getNumOfContinuedFractions(int maxN)
{
    int numOfContinuedFractions = 0;
    
    for (int N=2; N<=maxN; N++)
    {
        int root = (int)sqrt(double(N));;
        if (root*root == N)
        {
            continue;
        }
        else
        {
            if (getPeriod(N) % 2 == 1)
            {
                numOfContinuedFractions ++;
            }
        }
    }

    return numOfContinuedFractions;
}
    
int main()
{
    PE0064 pe0064;

    assert(4 == pe0064.getNumOfContinuedFractions(13));

    cout << pe0064.getNumOfContinuedFractions(10000);
    cout << " continued fractions for N<=10000 have an odd period." << endl;

    return 0;
}