백준 3825번: 은행수 [C++]

작성일 | In
골드 IV 골드 IV

문제

은행수
힌트가 전부 떠먹여주는 수학 문제입니다.

풀이

$(m, n) \dot (x, y) = (p, q)$라면 $(m^2 + n^2)(x^2 + y^2) = p^2 + q^2$이라고 힌트에 적혀 있습니다.
그런데 소수는 문제에서 설명한 8개의 약수만을 가지므로, 위 식을 만족하는 $(m, n)$의 순서쌍이 문제에 적힌 8개가 아니면 소수가 아닙니다.
다르게 말해 $p^2 + q^2$의 약수가 $1$ 또는 $p^2 + q^2$가 아닌 $m^2 + n^2$꼴로 표현된다면 $(p, q)$는 소수가 아닙니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int t;
    cin >> t;
    while (t--) {
        int m, n;
        cin >> m >> n;

        bool is_prime = true;

        int sum = m*m + n*n;
        int factor = 1;
        int k = 2;

        while (sum > 1) {
            if (sum % k == 0) {
                sum /= k;
                factor *= k;

                for (int i = 0; i*i <= factor; i++) {
                    if (not is_prime) break;
                    for (int j = 0; j <= i; j++) {
                        if (not is_prime) break;

                        int temp = i*i + j*j;
                        if (temp <= 1 or temp == (n*n + m*m)) continue;

                        if (factor % temp == 0) {
                            is_prime = false;
                            // cout << i << ' ' << j << '\n';
                        }
                    }
                }
            } else k++;
            if (not is_prime) break;
        }
        cout << (is_prime ? 'P' : 'C') << '\n';
    }
}

백준 3825번: 은행수 [C++]