Project Euler 포스팅 시작 + Problem 75

Project Euler 는 수학 계열의 고난도 알고리즘 (사실 알고리즘이랑 크게 상관 없는 문제도 있지만) 문제들을 연습할 수 있는 나름 좋은 문제 소스이다.

 

문제 유형이 PS랑 약간 다른데, 이런 식이다.

PS (백준, Codeforces 등) : 1초 내에 $N$ 이하의 소수를 전부 찾는 코드를 짜라. $N \leq 100,000$.

Project Euler (PE라고 줄이자) : 10만 1번째 소수는?

 

어쨌든 프로그래밍을 이용해서 해결하는 문제긴 하다. 

 

난이도는 %로 표시되는데,

5%~10%문제 : 단순 구현 문제 (에라토스테네스의 체 구현 같은거), 적당한 생각으로 풀 수 있는 문제들이 있다.

15%~ : 펜과 종이를 꽤 많이 써야 하는 문제가 나오기 시작한다.

25%~ : 수식을 잘 정리하거나, 수학적인 정리를 알아야 하는 문제들이 나온다.

35%~ : 지금 현재 내 실력으로 풀 수 있는 한계가 30~35% 정도 되는것 같은데, 꽤 오랜 시간 점화식을 생각한 후에도 줄여야 하는 문제 등등이 있었다.

 

1 minute rule 이라고, 코드는 "1분 이내에 돌아가는 것" 이 대략적인 기준이다. 물론 엄격한 것은 아니고, 무엇보다 사이트는 답만 요구하니까 사실 오래 걸려도 상관 없다. 정해가 그게 아니라는 것일 뿐... 언어마다 다른데, 아마 C 기준인 듯? 하지만 나는 Bigint를 짜고 싶지도 않고(...) Python 라이브러리가 유용하기 때문에 Python 등으로도 많이 풀 듯 하다.

---

Problem 75. Singular Integer Right Triangles

문제 링크

 

스포방지선

---

 

 

 

 

 

 

---

$1,500,000$ 이하의 정수들 중, 정확히 1개의 $a < b < c$ 가 존재해서, $a^2 + b^2 = c^2$, $a+b+c = L$ 을 만족하는 $L$의 개수를 세는 문제이다. 

직각삼각형의 세 변의 길이가 되는 피타고라스 순서쌍 (또는 피타고라스 삼조 라고 부른다) 에는 좋은 성질이 있다.

원시 피타고라스 삼조 라고 부르는데, 어떤 자연수 $(a, b, c)$ 가 피타고라스 삼조이면 임의의 자연수 $n$ 에 대하여 $(na, nb, nc)$ 도 피타고라스 삼조이며, 그 역도 성립한다는 것이다. 즉, 모든 피타고라스 삼조는 어떤 원시 피타고라스 삼조의 자연수배라는 것이다.

 

또한, Euclid Formula 라 하여, 다음의 성질이 성립한다.

$m > n > 0$ 일 때, $a = m^2 - n^2,\ b = 2mn,\ c = m^2 + n^2$ 는 피타고라스 삼조를 이룬다. 

특히, $m$과 $n$의 홀짝성이 다르고, $gcd(m, n)$ 이 1일 때 (즉, $m$, $n$ 이 서로소일 때) 위 공식은 원시 피타고라스 삼조를 생성한다. 이 명제의 증명은 나중에 따로 쓰기로 하자. (상당히 귀찮은 요소가 많다)

 

이제, 적당히 생각을 해보자. 어차피 $c = m^2 + n^2 < \frac{L}{2}$ 여야 하므로

$m < \sqrt{\frac{L}{2}}$ 까지의 $m$과 그보다 작은 $n$ 만 보면 충분하다.

어떤 $m_0, n_0$ 에 대하여, 원시 피타고라스 삼조가 생성된다면 (즉, 위에서 기술한 조건을 만족한다면), 이 생성된 원시 피타고라스 삼조를 $a, b, c$라고 하고, $a+b+c = t$ 라고 하자. 이때, $t$의 배수들은 모두 $nt = na+nb+nc$ 이므로 원시가 아닌 피타고라스 삼조의 합이 된다. chk[n*t]++를 쭉 돌면서 해주자.

 

이런 식으로, $m, n$ 으로부터 생성된 모든 원시 피타고라스 삼조들의 배수들을 모두 마킹하고 나면, 1부터 1,500,000 까지 돌면서 chk배열의 값이 1인 것들의 수를 세면 끝.

 

많아야 $m^2$ 의 몇 배 정도를 돌게 되며, $m^2 = 750,000$ 이므로 이 값은 매우 빠르게 계산될 것이다.

 

 

코드

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#define ll long long
#define gcd(A,B) (__gcd(A,B))
using namespace std;

const ll M = 1500000;
int chk[M+1];
int main()
{
    int max_m = (int)sqrt(750000);
    for (int m = 2; m<max_m; m++)
    {
        for (int n = 1; n<m; n++)
        {
            if ((m+n)%2 && (gcd(m,n)==1))
            {
                ll a = (ll)m*m-(ll)n*n;
                ll b = 2*(ll)m*n;
                ll c = (ll)m*m+(ll)n*n;
                ll tr = a+b+c;
                for (int i = 1; i*tr<=M; i++)
                    chk[i*tr]++;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i<=M; i++)
        ans += (chk[i]==1?1:0);
    cout << ans << '\n';
}

---

Execution Time : 17ms