백준 14398, 피타고라스 수

by

개요

문제 연결
계획 3, 그래프, 이분 매칭, 정수론
직각 삼각형의 빗변이 아닌 두 변을 형성하기 위해 두 개의 서로소 수를 짝지을 때 가장 큰 쌍 수를 찾으십시오.

입장

  1. 흥미로운 이분법 문제. 이 새로운 알고리즘을 배우면 응용 프로그램은 끝이 없습니다. 레벨업이 좋다 재미를 더합니다. 이것을 조합하는 방법을 모르면 공부합시다. 내용을 모르면 시작할 수 없고 무차별 대입을 해서 200을 노릴 수밖에 없다!
  2. 소수 쌍 문제와 비슷하지만 이진법과 일치법도 비슷하게 생각하면 됩니다. 이 사람을 어떻게 해야 합니까?
    1. 이 문제는 매우 특이하다. 현재 문장을 두 부분으로 나누지 않고 복사하면 하다.
    2. 연결 조건은 무엇입니까? 먼저 서로에게 두 수의 제곱의 합이 자연수의 제곱일 때 즉, sqrt(a×a+b×b)를 찾는다.
    3. 오류를 줄이기 위해 이진 검색 등을 사용할 수 있습니다. 자유롭게 0,1을 추가하고 int를 설정하십시오.
  3. 다음은 매칭인데, 매칭은 일반적인 바이너리 매칭과 동일합니다. 하지만 Ai-Bj 연결과 Bj-Ai 연결은 자신을 복제하는 집합을 사용하기 때문에 중복됩니다.그러니 일치하는 수를 반으로 나누면 됩니다.

의사 코드

for (i = 1~n)
    for (j = 1~n)
        if (i==j) continue
        if (gcd(a,b)!=1) continue
        c = int(sqrt(a*a+b*b)+0.1)
        if (c*c = a*a+b*b)
            adjoint(a).push(b)

can(a) {
    // 원하는 B 중에서
    for (b:graph(a))
        // 아무도 선택 안했거나
        // 선택한 숫자를 내쫓을 수 있을 때
        if (!B(b)||can(B(b))) {
            A(a)=b,B(b)=a
            return 1
        }
    return 0
}

match() {
    cnt=0
    for (i = 1~n)
        if (!A(i))
            cnt += can(i)
    return cnt
}

소스 코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define N 210
#define vec vector
#define pb push_back

using ld=long long;
int A(N),B(N);
bool vis(N);
vec<int> adj(N);

bool can(int a) {
    vis(a)=1;
    for (auto b:adj(a))
        if (!B(b)||!vis(B(b))&&can(B(b))) {
            A(a)=b,B(b)=a;
            return 1;
        }
    return 0;
}

int gcd(int a,int b) {
    int c;
    while(b) c=b,b=a%b,a=c;
    return a;
}

int match(int n) {
    int cnt=0;
    for (int i=1;i<=n;i++)
        if (!A(i)) {
            fill(vis,vis+N,0);
            cnt+=can(i);
        }
    return cnt/2;
}

int main() {
    int n;
    cin>>n;
    ld x(n+1);
    for (int i=1;i<=n;i++)
        cin>>x(i);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++) {
            if (i==j) continue;
            ld a=x(i),b=x(j);
            if (gcd(a,b)!=1) continue;
            ld v=a*a+b*b;
            ld c=ld(sqrt(v)+0.1);
            if (c*c==v)
                adj(i).pb(j);
        }
    cout<<match(n);
}