[백준 / BOJ] C++ 28683 피타! 피타! 피타츄!

28683번: 피타! 피타! 피타츄!

 

문제

https://www.acmicpc.net/problem/28683

28683번: 피타! 피타! 피타츄!

 

 

풀이

대회 당시에는 문제를 해결하지 못했다. 친구의 설명으로 문제를 해결하고 에디토리얼을 참고했다.

 

몇 가지 조건을 나누어 문제를 해결할 수 있다.

 

1. n이 제곱수인 경우

√n은 정수다. 임의의 정수 a에 대해 (√n, a, √(n+a^2))이 직각삼각형을 이루고, 두 변의 길이가 √n과 a로 정수이므로 무한하다.

 

2. n이 제곱수가 아닌 경우

나머지 두 변을 a, b라 했을 때 a, b가 모두 정수여야 한다. 여기서 조건을 다시 한번 나눌 수 있다.

 

2-1. 길이가 √n인 변이 빗변인 경우

빗변의 길이가 √n이라면 a ≤ b < √n이다. 그리고 a^2 + b^2 = n을 성립한다.

따라서 a를 1부터 √n까지 늘려가며 b^2 = n - a^2 가 제곱수인지 확인하면 된다.

 

2-2. 길이가 √n인 변이 빗변이 아닌 경우

빗변의 길이가 b, 나머지 두 변의 길이가 a, √n이라면 a^2 + n = b^2가 성립한다.

이 식을 정리하면 n = b^2 - a^2 = (b - a)(b + a)이다.

즉, 입력받은 n의 약수 중, 곱해서 n이 되는 쌍 중에 홀짝성이 같은 쌍의 개수를 구한다.

 

N의 범위가 int를 초과하기 때문에 이후에 모든 정수형 자료형은 long long을 사용했다.

제곱수인지 확인하는 법은 sqrt 함수를 사용했다. sqrt는 double 자료형을 반환하는데, 임의의 정수 a에 대해 sqrt(a)와 소수점 아래 값을 버린 (int)sqrt(a)가 같으면 a는 제곱수가 된다.

중복 처리는 set과 pair 자료구조를 사용했다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  ll n;
  cin >> n;
  // 1. N이 제곱수인 경우
  if (sqrt(n) == (ll)sqrt(n)) {
    cout << -1;
    return 0;
  }
  set<pair<ll, ll>> ans;
  // 2. N이 제곱수가 아닌 경우
  // 2-1. 길이가 √N인 변이 빗변인 경우
  for (ll i = 1; i <= sqrt(n); i++) {
    ll x = i;
    double y = sqrt(n - x * x);
    ll tmp = y;
    if (y == tmp) {
      if (x > tmp)
        swap(x, tmp);
      ans.insert({x, tmp});
    }
  }
  // 2-2. 길이가 √N인 변이 빗변이 아닌 경우
  vector<ll> divisor;
  for (ll i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      divisor.push_back(i);
      if (i != n / i)
        divisor.push_back(n / i);
    }
  }
  sort(divisor.begin(), divisor.end());
  for (ll i = 0; i < (divisor.size() + 1) / 2; i++) {
    if (divisor[i] % 2 == divisor[divisor.size() - i - 1] % 2)
      ans.insert({divisor[i], divisor[divisor.size() - i - 1]});
  }
  // 정답 출력
  cout << ans.size();
  return 0;
}