백준14398 피타고라스 수

작성일 | In

문제 링크

  • http://icpc.me/14398

사용 알고리즘

  • 이분매칭

풀이

$N \leq 200$이면 플로우를 의심해봐야 합니다.

막대기 두 개를 선택하는 것은 다음 3가지 경우 중 하나입니다.

  • 짝수 2개
  • 홀수 2개
  • 짝수 1개, 홀수 1개

짝수 2개를 고르는 것은 두 수가 서로소가 아니기 때문에 불가능합니다.
홀수 2개를 고르는 것을 생각해봅시다.
양의 정수 $a, b$에 대해 홀수 2개를 각각 $2a-1, 2b-1$이라고 합시다. 두 수를 제곱해서 더하면 $4(a^2+b^2-a-b)+2$가 나오고, 이 수는 2의 배수이면서 4의 배수가 아닙니다.
홀수 2개를 제곱해서 더하면 제곱수가 나오지 않기 때문에 홀수 2개를 선택하는 것도 불가능합니다.

짝수와 홀수가 각각 자신들끼리 연결되지 않으므로 이분 그래프로 모델링할 수 있고, 이분 매칭으로 문제를 풀 수 있습니다.

전체 코드

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
47
48
49
50
51
52
53
54
55
56
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define int long long
using namespace std;

typedef long long ll;

int n;
vector<int> a, b;

const int bias = 200;
vector<int> g[444];
int par[444];
int chk[444];

int dfs(int v){
    chk[v] = 1;
    for(auto i : g[v]){
        if(chk[i]) continue;
        chk[i] = 1;
        if(par[i] == -1 || dfs(par[i])){
            par[i] = v; return 1;
        }
    }
    return 0;
}

int isSquare(int x){
    int sq = (int)sqrt(x);
    return x == sq*sq;
}

int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=0; i<n; i++){
        int t; cin >> t;
        if(t & 1) a.push_back(t);
        else b.push_back(t);
    }
    for(int i=0; i<a.size(); i++) for(int j=0; j<b.size(); j++){
        if(__gcd(a[i], b[j]) == 1 && isSquare(a[i]*a[i] + b[j]*b[j])){
            g[i].push_back(j+bias);
        }
    }
    memset(par, -1, sizeof par);
    int ans = 0;
    for(int i=0; i<a.size(); i++){
        memset(chk, 0, sizeof chk);
        ans += dfs(i);
    }
    cout << ans;
}