pku3101 Astronomy

几天没敲代码。。手生了。。。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#include<cmath>
#include<cassert>
#include<cstring>
#include<iomanip>
using namespace std;

#ifdef _WIN32
#define i64 __int64
#define out64 "%I64d\n"
#define in64 "%I64d"
#else
#define i64 long long
#define out64 "%lld\n"
#define in64 "%lld"
#endif
/************ for topcoder by zz1215 *******************/
#define FOR(i,a,b)      for( int i = (a) ; i <= (b) ; i ++)
#define FFF(i,a)        for( int i = 0 ; i < (a) ; i ++)
#define FFD(i,a,b)      for( int i = (a) ; i >= (b) ; i --)
#define S64(a)          scanf(in64,&a)
#define SS(a)           scanf("%d",&a)
#define LL(a)           ((a)<<1)
#define RR(a)           (((a)<<1)+1)
#define pb              push_back
#define CL(Q)           while(!Q.empty())Q.pop()
#define MM(name,what)   memset(name,what,sizeof(name))
#define read            freopen("in.txt","r",stdin)
#define write           freopen("out.txt","w",stdout)
#define MAX 10000
#define base 10000
#define digit 4
const int inf = 0x3f3f3f3f;
const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;
const double oo = 10e9;
const double eps = 10e-9;
const double pi = acos(-1.0);
const int maxn = 10001;

struct bigint
{
    int c[MAX];
    int len;
    void init()
    {
        len = 0;
        memset(c,0,sizeof(c));
    }

    bigint()
    {
        init();
        len = 1;
    }

    bigint(int n)
    {
        init();
        do {
            c[len++] = n%base;
            n /= base;
        } while(n);
    }

    bigint(char* s)
    {
        init();
        for(int i=strlen(s);i>=0;i--)
            c[i/4] = c[i/4]*10 + c[i] - '0';
    }

    bigint(const bigint & n)
    {
        *this = n;
    }

    bigint & operator = (const bigint & a)
    {
        len = a.len;
        for(int i=0;i<len;i++) c[i] = a.c[i];
        return *this;
    }

    bigint operator + (const bigint & a) const
    {
        bigint t;
        t.len = max(a.len,len);
        for(int i=0;i<t.len;i++)
            t.c[i] = c[i]+a.c[i];
        for(int i=0;i<t.len;i++)
            t.c[i+1] += t.c[i]/base, t.c[i] %= base;
        if(t.c[t.len]) t.len++;
        return t;
    }

    bigint operator * (const bigint & a) const
    {
        bigint t;
        t.len = a.len+len+2;
        for(int i=0;i<len;i++) for(int j=0;j<a.len;j++)
        {
            t.c[i+j] += c[i]*a.c[j];
            t.c[i+j+1] += t.c[i]/base;
            t.c[i+j] %= base;
        }
        for(int i=0;i<t.len;i++)
        {
            t.c[i+1] += t.c[i]/base;
            t.c[i] %= base;
        }
        while(!t.c[t.len-1]) t.len--;
        return t;
    }

    void out()
    {
        printf("%d",c[len-1]);
        for(int i=len-2;i>=0;i--)
        {
            printf("%04d",c[i]);
        }
    }

    friend ostream & operator << (ostream & os,const bigint & a)
    {
        os << a.c[a.len - 1];
        for(int i = a.len - 2;i>=0;i--)
        {
            os.width(digit);
            os.fill('0');
            os << a.c[i];
        }
        return os;
    }

    friend istream & operator >> (istream & is,bigint & a)
    {
        char s[MAX*4+1];
        is>>s;
        bigint t(s);
        a = t;
        return is;
    }
};

bigint ans1,ans2;
int n;
int s[maxn];
int sx[maxn];
vector<int>p;
vector<int>v;
vector<int>t;
int u[1001];
int d[1001];

i64 gcd(i64 _a, i64 _b)
{
    if (!_a || !_b)
    {
        return max(_a, _b);
    }
    i64 _t;
    while ((_t = _a % _b))
    {
        _a = _b;
        _b = _t;
    }
    return _b;
}

bool isp(int x)
{
	for(int i=0;p[i]*p[i]<=x;i++)
	{
		if(x%p[i]==0)
		{
			return false;
		}
	}
	return true;
}

void initp()
{
	p.clear();
	p.pb(2);
	for(int i=3;i<100000;i++)
	{
		if(isp(i))
		{
			p.pb(i);
		}
	}
	return ;
}

void get(int x)
{
	MM(sx,0);
	int temp = u[x];
	for(int i=0;p[i]*p[i]<=temp;i++)
	{
		while(temp%p[i]==0)
		{
			sx[p[i]]++;
			temp/=p[i];
		}
	}
	if(temp>1)
	{
		assert(isp(temp));
		sx[temp]++;
	}
	temp = d[x];
	for(int i=0;p[i]*p[i]<=temp;i++)
	{
		while(temp%p[i]==0)
		{
			sx[p[i]]--;
			temp/=p[i];
		}
	}
	if(temp>1)
	{
		assert(isp(temp));
		sx[temp]--;
	}
	return ;
}

int main()
{
	initp();
	int temp;
	while(cin>>n)
	{
		v.clear();
		t.clear();
		for(int i=1;i<=n;i++)
		{
			cin>>temp;
			v.pb(temp);
		}
		sort(v.begin(),v.end());
		temp = v[0];
		t.pb(temp);
		for(int i=1;i<v.size();i++)
		{
			if(v[i]!=temp)
			{
				temp = v[i];
				t.pb(temp);
			}
		}
		n = t.size()-1;
		for(int i=1;i<=n;i++)
		{
			u[i]=t[0]*t[i];
			d[i]=t[i]-t[0];
			d[i]*=2;
			temp=gcd(u[i],d[i]);
			u[i]/=temp;
			d[i]/=temp;
		}

		for(int i=0;i<maxn;i++)
		{
			s[i]=-inf;
		}
		for(int i=1;i<=n;i++)
		{
			get(i);
			for(int k=0;k<maxn;k++)
			{
				s[k]=max(s[k],sx[k]);
			}
		}
		ans1 = ans2 = 1;
		for(int i=1;i<maxn;i++)
		{
			if(s[i]>0)
			{
				for(int k=1;k<=s[i];k++)
				{
					ans1 = ans1 * i;
				}
			}
			else if(s[i]<0)
			{
				s[i]=-s[i];
				for(int k=1;k<=s[i];k++)
				{
					ans2 = ans2 * i;
				}
			}
		}

		cout<<ans1<<" "<<ans2<<endl;
	}

    return 0;
}