# [Silver I] 여섯 방정식 [문제 링크](https://www.acmicpc.net/problem/9765) ## 문제 설명 <p>여섯 개의 간단한 방정식이 주어진다. 이때, x₁, x₂, x₃, x₅, x₆, x₇를 찾는 프로그램을 작성하시오. x₁, x₂, x₃, x₅, x₆, x₇은 2보다 크거나 같고, 20,000,000보다 작거나 같은 소수이다. 여섯 방정식은 아래와 같다.</p> <ul> <li>c₁ = x₁x₂</li> <li>x₄ = c₄x₁</li> <li>c₃ = x₆x₇</li> <li>x₈ = x₇c₂</li> <li>c₅ = x₂x₃</li> <li>c₆ = x₆x₅</li> </ul> <p>c₁, c₂, c₃, c₄, c₅, c₆은 양의 정수로 (20,000,000)²을 넘지 않는다. c₁, c₂, c₃, c₄, c₅, c₆이 주어졌을 때, x₁, x₂, x₃, x₅, x₆, x₇을 푸는 프로그램을 작성하시오. 항상 풀 수 있는 방정식만 입력으로 주어진다. </p> ## 입력 <p>첫째 줄에 c₁, c₂, c₃, c₄, c₅, c₆이 주어진다. (c₁ ≠ c₅, c₃ ≠ c6)</p> ## 출력 <p>x₁, x₂, x₃, x₅, x₆, x₇ 를 공백으로 구분해 출력한다. 가능한 답이 여러 가지인 경우, 아무거나 출력한다.</p> ## 풀이 유클리드 호제법으로 c1과 c5, c3와 c6 사이의 최대공약수를 찾아 x2, x6를 찾아 놓고 방정식의 해를 출력하면 됩니다. 브루트포스로 2000만까지 소수판정해서 x2와 x6를 찾는 방법도 300ms 정도에 풀립니다. ``` c++ #include<bits/stdc++.h> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(0); cin.tie(0); ll c1, c2, c3, c4, c5, c6; cin >> c1 >> c2 >> c3 >> c4 >> c5 >> c6; ll gcd1 = gcd(c1, c5); ll gcd2 = gcd(c3, c6); cout << c1/gcd1 << ' ' << gcd1 << ' ' << c5/gcd1 << ' ' << c6/gcd2 << ' ' << gcd2 << ' ' << c3/gcd2; } ```