백준 14398 / C++

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

14398번: 피타고라스 수

 

[ 풀이 ] 

이분그래프 모델링을 해보자. 수학적 지식이 좀 필요하다. 

만약 a^2+b^2=c^2에서 a, b가 짝수라면, gcd에 모순이다.

a, b가 모두 홀수라면 홀수의 제곱은 4로 나눈 나머지가 항상 1이다. 

따라서 c^2은 4로 나눈 나머지가 2인 짝수가 되어 모순이다. ( 제곱수는 mod4로 0,1만 가능)

(원시 피타고라스 세쌍을 알고 있다면 해가 (m^2-n^2, 2mn)꼴이므로 적어도 하나는 짝수임을 알 수도 있다. )

아무튼 결국 a,b는 반드시 한개는 짝수, 한개는 홀수이다. 

따라서 이분그래프로 나뉘고 제곱수면 연결시켜보면서 최대매칭수를 구해주면 된다. 

 

[ Code ]

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<ll>odd, even;
ll n, a[222], par[222], vis[222];

int is_sq(ll a, ll b) {
	ll c = sqrt(a * a + b * b);
	return (c * c == a * a + b * b) && gcd(a, b) == 1;
}

int match(int x) {
	for (int nx : even) {
		if (vis[nx] || !is_sq(a[x], a[nx]))continue;
		vis[nx] = 1;
		if (!~par[nx] || match(par[nx])) {
			par[nx] = x;
			return 1;
		}
	}
	return 0;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		if (a[i] % 2) odd.push_back(i);
		else even.push_back(i);
	}
	int ans = 0;
	memset(par, -1, sizeof(par));
	for (int i : odd) {
		memset(vis, 0, sizeof(vis));
		ans += match(i);
	}
	cout << ans;
}