[백준] 9765 여섯 방정식

 

참 어려워 보이는 문제다

근데 생각해보면 쉬운 문제다

물론 long long 안써서 처음에 틀렸다 ㅎㅎ

 

먼저 우리가 알아야할 x들은 소수라는 점을 기억하자

그럼 c1,c3,c5,c6은 소수 2개의 곱이므로 유일한 수 2개가 있을 것이다.

 

결국 완탐하면 된다!

이 문제에서 x4랑 x8은 의미없다 쓰지 않는다

 

완전탐색을 할 때

어떤 수 2개를 곱해서 c가 되야하므로 i*i<=c까지 보면 된다!

근데 이 때 x는 2 이상이므로 x와 c가 같다면 1,x가 나오므로 건너 뛰어야 한다

마지막으로 폭풍의 6중 for문으로 값을 확인해보자!

 

소수의 개념을 알면 쉽게 풀 수 있다!

그리고 범위 조심하자

 

소스코드

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
ll c1,c2,c3,c4,c5,c6;
 
void solve(ll num,vector<ll> &vt1,vector<ll> &vt2){
    for(ll i=2;i*i<=num;i++){
        if(num!=i && num%i==0){
            vt1.push_back(i);
            vt1.push_back(num/i);
            vt2.push_back(i);
            vt2.push_back(num/i); 
            return;
        }
    }
}
int main(){
    cin>>c1>>c2>>c3>>c4>>c5>>c6;
    vector<ll> x1,x2,x3,x4,x5,x6,x7,x8;
 
    solve(c1,x1,x2);
    solve(c3,x6,x7);
    solve(c5,x2,x3);
    solve(c6,x6,x5);
 
    for(int a=0;a<x1.size();a++){
        for(int b=0;b<x2.size();b++){
            for(int c=0;c<x3.size();c++){
                for(int d=0;d<x5.size();d++){
                    for(int e=0;e<x6.size();e++){
                        for(int f=0;f<x7.size();f++){
                            if(x1[a]*x2[b]==c1 && x6[e]*x7[f]==c3 && x2[b]*x3[c]==c5 && x5[d]*x6[e]==c6){
                                printf("%lld %lld %lld %lld %lld %lld\n",x1[a],x2[b],x3[c],x5[d],x6[e],x7[f]);
                                return 0;
                            }
                        }
                    }
                }
            }
        }
    }
}