Divisors of Two Integers CodeForces - 1108B （数学+思维）

Recently you have received two positive integer numbers xx and yy. You forgot them, but you remembered a shuffled list containing all divisors of xx (including 11 and xx) and all divisors of yy (including 11 and yy). If dd is a divisor of both numbers xx and yy at the same time, there are two occurrences of dd in the list.

For example, if x=4x=4 and y=6y=6 then the given list can be any permutation of the list [1,2,4,1,2,3,6][1,2,4,1,2,3,6]. Some of the possible lists are: [1,1,2,4,6,3,2][1,1,2,4,6,3,2], [4,6,1,1,2,3,2][4,6,1,1,2,3,2]or [1,6,3,2,4,1,2][1,6,3,2,4,1,2].

Your problem is to restore suitable positive integer numbers xx and yy that would yield the same list of divisors (possibly in different order).

It is guaranteed that the answer exists, i.e. the given list of divisors corresponds to some positive integers xx and yy.

Input

The first line contains one integer nn (2≤n≤1282≤n≤128) — the number of divisors of xxand yy.

The second line of the input contains nn integers d1,d2,…,dnd1,d2,…,dn (1≤di≤1041≤di≤104), where didi is either divisor of xx or divisor of yy. If a number is divisor of both numbers xxand yy then there are two copies of this number in the list.

Output

Print two positive integer numbers xx and yy — such numbers that merged list of their divisors is the permutation of the given list of integers. It is guaranteed that the answer exists.

Example

Input

10

10 2 8 1 2 4 1 20 4 5

Output

20 8

题意：
给定一个数组，这个数组包含了两个正整数a和b的所有因子，包括1和a，b，如果x同为a和b的因子，那么数组中x出现两次。
让求出a和b的数值。
思路：首先对数组进行排序，那么最大值一定是我们a和b中的一个（原因自行思考）。那么我们最大值是a。
然后我们暴力的把a的所有因子都求出来，从数组中删除一次，然后剩下的数组中的最大值就是我们要找的b。
细节见代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#define sz(a) int(a.size())

#define all(a) a.begin(), a.end()

#define rep(i,x,n) for(int i=x;i<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

#define MS0(X) memset((X), 0, sizeof((X)))

#define MSC0(X) memset((X), '\0', sizeof((X)))

#define pb push_back

#define mp make_pair

#define fi first

#define se second

#define eps 1e-6

#define gg(x) getInt(&x)

#define db(x) cout<<"== [ "<<x<<" ] =="<<endl;

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

ll powmod(ll a,ll b,ll MOD){ll ans=;while(b){if(b%)ans=ans*a%MOD;a=a*a%MOD;b/=;}return ans;}

inline void getInt(int* p);

const int maxn=;

const int inf=0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll n;

ll a[maxn];

int main()

{

    gbtb;

    cin>>n;

    map<ll,ll> m;

    repd(i,,n)

    {

        cin>>a[i];

        m[a[i]]++;

    }

    sort(a+,a++n);

    ll x=1ll;

    ll y=1ll;

    y=a[n];

    for(ll i=;i<=y;i++)

    {

        if(y%i==)

            m[i]--;

    }

    for(ll i=;i>=;i--)

    {

        if(m[i]==)

        {

            x=i;

            break;

        }

    }

    cout<<x<<" "<<y;

    return ;

}

inline void getInt(int* p) {

    char ch;

    do {

        ch = getchar();

    } while (ch == ' ' || ch == '\n');

    if (ch == '-') {

        *p = -(getchar() - '');

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  - ch + '';

        }

    }

    else {

        *p = ch - '';

        while ((ch = getchar()) >= '' && ch <= '') {

            *p = *p *  + ch - '';

        }

    }

}

巴特西

Divisors of Two Integers CodeForces - 1108B （数学+思维）

最新文章

热门文章