조건에 맞는 기약분수의 갯수

프로젝트 오일러의 71~73번 문제는 비슷하게 생겼는데, 실제로는 서로 상당히 다른 문제들이다.

서로 비교해보면 많은 생각을 하게 하는 문제들이다.

 

71번

주어진 범위의 기약분수 중에서 \( \frac {3}{7} \)보다 작으면서 가장 큰 분수의 분자를 찾는 문제다.

 

 

주어진 범위가 무려 백만까지므로 무식하게 보면 백만(Mega)×백만＝1Tera^[각주:1]번 루프를 돌리면 답을 찾을 수 있다.

하지만, 조금만 생각해보면 각 분모별로 \( \frac {3}{7} \)에 가까운 기약분수 하나씩만 비교해보면 된다.

 

간단하게 만들어보면 아래와 같다. 최대공약수 코드는 앞 포스팅의 코드를 활용.

 

#include <cstdio>
#include <cmath>
#include <algorithm>

size_t GCDfast(size_t x, size_t y)
{
	if (!x || !y) return (x + y);

	unsigned long cf2, temp;
	_BitScanForward64(&cf2, x | y);

	_BitScanForward64(&temp, x);
	x >>= temp;

	for (;;) {
		_BitScanForward64(&temp, y);
		y >>= temp;

		if (x == y) break;
		if (x > y) std::swap(x, y);
		if (x == 1) break;

		y -= x;
	}

	return x << cf2;
}

int main()
{
	size_t num = 0;
	size_t den = 1;

	for (size_t d = 3; d <= 1000000; ++d) {
		size_t n = 3 * d / 7;
		while (n && ((GCDfast(n, d) != 1) || (d * 3 == n * 7))) {
			--n;
		}
		if (!n) {
			continue;
		}

		if (num * d < den * n) {
			num = n;
			den = d;
		}
	}
}

 

72번

이 문제는 71번과 비슷한 것 같은데, 사실은 완전히 다르다.

백만 이하의 분모를 갖는 모든 진분수의 갯수를 세는 것.

\( \frac {1}{2} \)과 \( \frac {2}{4} \)는 같은 값이므로 한번만 세면 된다.

 

 

이번에야말로 백만×백만 번의 루프를 돌려 기약분수인 경우 즉, 두 수가 서로소인 경우를 다 더하면 될 것 같다.

하지만, (그렇게 풀어도 되기는 한데) 그렇게 푸는 문제가 아니다.

 

이전 글에서 언급한 오일러의 \( \phi(n) \)를 활용해서 각 분모별로 서로소인 수의 개수를 다 더하면 된다.

참고로, 결과값이 너무 커서 32비트 변수만 사용하면 올바른 결과를 얻을 수 없다.

 

#include <cstdio>
#include <cmath>
#include <map>

typedef std::map<size_t, size_t> FactMap;

void Factorize(size_t n, FactMap& fact)
{
    fact.clear();
    if (!n) { return; }

    while (!(n & 1)) {
        ++fact[2];
        n >>= 1;
    }

    while (n > 2) {
        size_t f;

        const size_t range = (size_t)sqrt(n);
        for (f = 3; f <= range; f += 2) {
            if (!(n % f)) {
                break;
            }
        }
        if (!(n % f)) {
            ++fact[f];
            n /= f;
        }
        else {
            ++fact[n];
            n = 1;
        }
    }
}

size_t CalcPhi(const size_t n)
{
    FactMap fact;
    Factorize(n, fact);

    if (fact.empty()) {
        return 0;
    }

    size_t ret = 1;
    FactMap::const_iterator it = fact.begin();
    while (it != fact.end()) {

        const size_t p = it->first;
        const size_t q = it->second;

        size_t tmp = 1;
        for (size_t i = 1; i < q; ++i) {
            tmp *= p;
        }

        ret = ret * tmp * (p - 1);

        ++it;
    }

    return ret;
}

int main()
{
    size_t sum = 0;
    for (size_t i = 2; i < 1000001; ++i) {
        sum += CalcPhi(i);
    }

    printf("%zu\n", sum);
}

 

73번

주어진 범위의 기약분수에서 \( \frac {1}{3} \) 초과, \( \frac {1}{2} \) 미만인 모든 분수의 갯수를 세는 문제이다.

 

 

이 문제는 뭔가 72번을 활용할 수 있을 것 같은 느낌이 든다.

\( \phi(n) \)를 잘 활용하면 될 것 같은 생각이 든다면 틀렸다.

그냥 71번를 확장해서 범위를 선정한 뒤, 일일이 비교해서 카운트를 증가시켜야 한다.

 

#include <cstdio>
#include <cmath>
#include <algorithm>

size_t GCDfast(size_t x, size_t y)
{
	if (!x || !y) return (x + y);

	unsigned long cf2, temp;
	_BitScanForward64(&cf2, x | y);

	_BitScanForward64(&temp, x);
	x >>= temp;

	for (;;) {
		_BitScanForward64(&temp, y);
		y >>= temp;

		if (x == y) break;
		if (x > y) std::swap(x, y);
		if (x == 1) break;

		y -= x;
	}

	return x << cf2;
}

int main()
{
	size_t count = 0;
	const static size_t range = 12000;

	for (size_t i = 4; i <= range; ++i) {
		const size_t range1 = i / 3;
		const size_t range2 = i / 2;

		for (size_t n = range1; n <= range2; ++n) {
			//1. 1/3 < n/i < 1/2 이면서
			//2. 기약분수인가
			if (i < (3 * n) && (2 * n) < i && (GCDfast(n, i) == 1)) {
				++count;
			}
		}
	}

	printf("%zu\n", count);
}

 

 

1. 물론 trillion이 정확한 표현임 [본문으로]