제곱근을 연분수로 나타낼 때 반복 주기가 홀수인 경우 세기

[eng][kor]

나는 이렇게 풀었다.


1) 무리수가 포함된 분수( 같은 ) 를 다룰 타입이 필요했다. 이 타입을 대충 라고 하자. 이 는 분모유리수, 분모무리수, 분자유리수, 분모무리수, 그리고 그냥 자연수 하나 이렇게 다섯개의 멤버를 갖고 있다.

2) 문제 예제를 보면 다음의 식이 반복되는 것을 알 수 있다.

유리화() = number +

역수( ) = number +

…

3) 유리화 함수와 역수 함수를 짠다.

4) 반복 감지는 이번에 구한 가 시작 와 같은지 체크하면 됨.


어떻게 풀었는지 정리해 보면 간단한데, 생각하기까지 많은 시간이 걸린다.

실행시간 0.623 초.

/*
 	Problem 64 - Odd period square roots
*/
	
#include <iostream>
#include <ctime>
#include <cmath>
#include <vector>

using namespace std;

class SquareRoot
{
	private :
	int n;

	public :
	SquareRoot() {};
	SquareRoot( int _n) { n = _n; }
	int getn() { return n; }
	void print()
	{
		cout << "sq(" << n << ")";
	}
};

int getnearby( SquareRoot sr)
{
	int nearby;
	for(int i=1;; i++) { if (pow(i, 2) <= sr.getn() && pow(i+1, 2) >= sr.getn()) { nearby = i; break; } }
	return nearby;
}

class Fraction
{
	private :
	// denominator
	SquareRoot dsr; int dn; 
	// numerator
	SquareRoot nsr; int nn;
	// n
	int n; SquareRoot sr;

	public :
	Fraction() {}

	void set( SquareRoot _sr, int _n, SquareRoot _dsr, int _dn, SquareRoot _nsr, int _nn)
	{
		sr = _sr; n = _n; dsr = _dsr; dn =_dn; nsr = _nsr; nn = _nn;
	}

	Fraction getConversed()
	{
		Fraction f;
		f.set( NULL, 0, nsr, nn, dsr, dn);
		return f;
	}

	Fraction getRationalized()
	{
		Fraction f;
		// intermediate
		int f_dn = (dsr.getn() - ( dn * dn)) / nn;
		SquareRoot f_nsr( dsr.getn());
		int f_nn = (dn * -1);
		int nearby = getnearby( dsr);
	
		// set final
		int f_n = (int)((nearby + f_nn) / f_dn);
		f.set( NULL, f_n, NULL, f_dn, f_nsr, f_nn - (f_n * f_dn));
		return f;
	}

	Fraction copy()
	{
		Fraction f;
		f.set( sr, n, dsr, dn, nsr, nn);
		return f;
	}

	bool hasSameFractionWith( Fraction f)
	{
		return 
			((dsr.getn() == f.getdsr().getn()) && ( dn == f.getdn()) 
			&&
			(nsr.getn() == f.getnsr().getn()) && ( nn == f.getnn()));
	}

	int getn() { return n; }
	SquareRoot getdsr() { return dsr; }
	int getdn() { return dn; }
	SquareRoot getnsr() { return nsr; }
	int getnn() { return nn; }

	void print()
	{
		cout << "(";
		if( sr.getn() != 0) {  sr.print(); }
		if( n != 0) { cout << "+" << n; }
		cout << ") + (";

		if( nsr.getn() != 0) { nsr.print(); }
		if( nn != 0) { cout << "+" << nn; }
		cout << "/";
		
		if( dsr.getn() != 0) { dsr.print(); }

		if( dn != 0) {
			if( dn > 0 ) { cout << "+" << dn; }
			else { cout << dn; }
		}
		cout << ")";
	}

};

Fraction getFirstFraction( int n)
{
	SquareRoot s(n);
	int nearby = getnearby( s);
	Fraction f;
	f.set( NULL, nearby, s, (-1)*nearby, NULL, 1);
	return f;
}

int main(int argc, char** argv)
{
	clock_t begin = clock();
	
	/* starting code */
/*
	Fraction f0 = getFirstFraction(23);
	f0.print(); cout << endl;
	Fraction rf0 = f0.getRationalized();
	rf0.print(); cout << endl;

	Fraction f1; f1 = rf0.getConversed();
	f1.print(); cout << endl;
	Fraction rf1 = f1.getRationalized();
	rf1.print(); cout << endl;
	*/

	int oddcnt = 0;
	for(int i=1; i<=10000; i++)
	{
		if( sqrt(i) == floor( sqrt(i))) { continue; }
		
		Fraction first = getFirstFraction( i);
		int firstN = first.getn();

		int seq = 0;
		Fraction next = first.copy();
		while( true) {
			seq++;
			next = next.getRationalized();
			next = next.getConversed();
			if (next.hasSameFractionWith( first)) { break; }
		}
//		cout << "i=" << i << " seq=" << seq << endl;
		if( seq%2 == 1) { oddcnt++; }
	}

	cout << "oddcnt = " << oddcnt << endl;
	/* end of code */
	clock_t end = clock();
	std::cout << "elapsed time=" << double(end - begin) / CLOCKS_PER_SEC << std::endl;
	return 0;
}