하 레이팅 1600짜리 문제 풀어봤다 드디어 ㅠㅠ



문제 : https://codeforces.com/contest/1350/problem/C


뭔가 필요 이상으로 복잡하게 푼거같은데 그래도 뿌듯하네


코드

-------------------

#include <iostream>

#include <vector>

#include <algorithm>


using namespace std;


int main() {

    int n;

    long long GCD=1;

    cin >> n;

    

    vector<int> a(n);

    

    int i,j;

    int maxA = 0;

    for(i=0 ; i<n ; i++)

    {

        cin >> a[i];

        if(maxA < a[i]) maxA = a[i];

    }

    vector<int> primes(1);

    primes[0]=2;

    for(i=3 ; i<=maxA ; i++)

    {

        bool flag = false;

        for(j=0 ; j<primes.size() ; j++)

        {

            if(i % primes[j] == 0)

            {

                flag = true;

                break;

            }

        }

        if(!flag) primes.push_back(i);

    }

    if(maxA != 1)

    {

        for(i=0 ; i<primes.size() ; i++)

        {

            vector<int> Powers;

            int failTest = 0;

            for(j=0 ; j<n ; j++)

            { 

                int temp = a[j];

                int curPower = 0;

                while(1)

                {

                    if(temp % primes[i] == 0)

                    {

                        curPower ++;

                        temp/=primes[i];

                    }

                    else break;

                }

                if(curPower == 0) failTest++;

                if(failTest == 2) break;

                Powers.push_back(curPower);

            }

            if(failTest != 2)

            {

                sort(Powers.begin(), Powers.end());

                for(j=1 ; j<=Powers[1] ; j++) 

                {

                    GCD *= primes[i];

                }

            }

        }

    }

    cout << GCD;

    return 0;

}