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