POJ 3101 素数分解+大数

题目

Astronomy
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 5643 Accepted: 1252
Description

There are n planets in the planetary system of star X. They orbit star X in circular orbits located in the same plane. Their tangent velocities are constant. Directions of orbiting of all planets are the same.

Sometimes the event happens in this planetary system which is called planet parade. It is the moment when all planets and star X are located on the same straight line.

Your task is to find the length of the time interval between two consecutive planet parades.

Input

The first line of the input file contains n — the number of planets (2 ≤ n ≤ 1 000).

Second line contains n integer numbers ti — the orbiting periods of planets (1 ≤ ti ≤ 10 000). Not all of ti are the same.

Output

Output the answer as a common irreducible fraction,separate numerator and denominator by a space.

Sample Input

3
6 2 3
Sample Output

3 1

题意

有一个星系，知道每个行星的周期，求他们可以在一条直线上的最小周期。

题解

假设有两个行星
假设T为相遇的时间，有

t1和t2为周期，L为2*pi。
这两个行星的角速度之差为

记这个数为分式c/b，那么可以知道最小公倍数应该是所有分式的最小公倍数。
有定理：

那么问题就转化成了求数的LCM和GCD，由于数字太大。我们要用素数分解定理把分子拆成素数的幂次和。中间如果直接用大数乘会超时。先拆分最后用大数去乘。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <string>
#include <set>
#include <cmath>
#include <map>
#include <queue>
#include <sstream>
#include <vector>
#include <iomanip>
#define m0(a) memset(a,sizeof(a))
#define mm(a) memset(a,0x3f,sizeof(a))
#define m_1(a) memset(a,-1,sizeof(a))
#define f(i,a,b) for(i = a;i<=b;i++)
#define fi(i,b) for(i = a;i>=b;i--)
#define lowbit(a) ((a)&(-a))
#define FFR freopen("data.in","r",stdin)
#define FFW freopen("data.out","w",stdout)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef long double ld;
const ld PI = acos(-1.0);

using namespace std;
#define SIZE (10000)
int G[SIZE+10];
int a[SIZE+10];

#define LEN 1000
#define MOD 10000

//定义了+ - * / % = == != >> << < > <= >= += -= *= /= %= print length pow等操作
//注意长度是否够用！！
struct INT {
    int num[LEN],len;
    bool sign;
    inline INT(long long x = 0) {
        *this = x;
    }
    inline INT(const string &str) {
        *this = str;
    }
    inline INT(const int a[],int b,bool c) {
        memcpy(num,sizeof num);
        len = b; sign = c;
    }
    inline INT &operator =(const string &str) {
        int start = 0;
        len = 0; sign = false;
        memset(num,0,sizeof num);
        if (str[0] == '-') sign = true,start = 1;
        while (str[start] == '0') start++;
        for (int i = str.length() - 1; i >= start; i -= 4,len++)
            for (int j = max(start,i - 3); j <= i; j++)
                num[len] = (num[len] << 3) + (num[len] << 1) + str[j] - '0';
        if (!len) sign = false;
        if (len) len--;
        return *this;
    }
    inline INT &operator =(long long x) {
        len = 0; sign = false;
        memset(num,sizeof num);
        if (x < 0) sign = true,x = -x;
        while (x)
            num[len++] = x % MOD,x /= MOD;
        if (len) len--;
        return *this;
    }
    inline int length() const {
        int re = len << 2,t = num[len];
        while (t) t /= 10,re++;
        return re;
    }
    inline void print() {
        if (sign) putchar('-');
        printf("%d",num[len]);
        for (int i = len - 1; i >= 0; i--)
            printf("%04d",num[i]);
    }
    inline friend void print_to_string(const INT &x,string &y) {
        stringstream stream;
        stream << x;
        stream >> y;
    }
    inline friend INT pow(const INT &x,int y) {
        INT re = 1,_x = x;
        while (y) {
            if (y & 1)
                re *= _x;
            y >>= 1;
            _x *= _x;
        }
        return re;
    }
    inline friend INT pow(const INT &x,const INT &y) {
        INT re = 1,_x = x,_y = y;
        while (_y != 0) {
            if (_y.num[0] & 1)
                re *= _x;
            _y = shr(_y);
            _x *= _x;
        }
        return re;
    }
    inline friend istream &operator >> (istream &in,INT &x) {
        string str;
        in >> str;
        x = str;
        return in;
    }
    inline friend ostream &operator <<(ostream &out,const INT &x) {
        if (x.sign) out << '-';
        out << x.num[x.len];
        for (int i = x.len - 1; i >= 0; i--)
            out.fill('0'),out.width(4),out << x.num[i];
        return out;
    }
    inline INT operator -() const {
        return INT(num,len,!sign);
    }
    inline friend INT abs(const INT &x) {
        return INT(x.num,x.len,false);
    }
    inline friend bool operator <(const INT &x,const INT &y) {
        if (x.sign ^ y.sign) return x.sign;
        int lx = x.length(),ly = y.length();
        if (lx == ly) {
            for (int i = x.len; i >= 0; i--)
                if (x.num[i] != y.num[i])
                    return (x.num[i] < y.num[i]) ^ x.sign;
            return false;
        }
        return (lx < ly) ^ x.sign;
    }
    inline friend bool operator >(const INT &x,const INT &y) { return y < x; }
    inline friend bool operator <=(const INT &x,const INT &y) { return !(y < x); }
    inline friend bool operator >=(const INT &x,const INT &y) { return !(x < y); }
    inline friend bool operator ==(const INT &x,const INT &y) { return !(x < y || y < x); }
    inline friend bool operator !=(const INT &x,const INT &y) { return !(x == y); }

    inline friend INT operator +(const INT &x,const INT &y) {
        if (x.sign ^ y.sign)
            return x - (-y);
        INT re;
        re.sign = x.sign;
        re.len = max(x.len,y.len);
        for (int i = 0; i <= re.len; i++) {
            re.num[i] += x.num[i] + y.num[i];
            re.num[i + 1] = re.num[i] / MOD;
            re.num[i] %= MOD;
        }
        if (re.num[re.len + 1]) re.len++;
        return re;
    }
    inline friend INT operator -(const INT &x,const INT &y) {
        if (x.sign ^ y.sign)
            return x + (-y);
        INT re,_y = y;
        re.sign = _x < _y;
        if (re.sign ^ _x.sign)
            swap(_x,_y);
        for (int i = 0; i <= _x.len; i++) {
            re.num[i] += _x.num[i] - _y.num[i];
            if (re.num[i] < 0)
                re.num[i] += MOD,re.num[i + 1]--;
        }
        re.len = _x.len;
        while (!re.num[re.len] && re.len >= 0) re.len--;
        return re;
    }
    inline friend INT operator *(const INT &x,const INT &y) {
        INT re,_y = y;
        while (_y != 0) {
            if (_y.num[0] & 1)
                re += _x;
            _y = shr(_y);
            _x += _x;
        }
        if (y.sign) re.sign ^= 1;
        return re;
    }
    inline friend INT operator /(const INT &x,const INT &y) {
        if ((!y.len && !y.num[0]) || (!x.len && !x.num[0]) || abs(x) < abs(y)) { return INT(); }
        INT re,left,_y = abs(y);
        re.sign = x.sign ^ y.sign;
        re.len = x.len - y.len + 1;
        left.len = -1;
        for (int i = x.len; i >= 0; i--) {
            memmove(left.num + 1,left.num,sizeof(left.num) - sizeof(int));
            left.len++;
            left.num[0] = x.num[i];
            int l = 0,r = MOD - 1,mid;
            if (left < y) r = 1;
            while (l < r) {
                mid = (l + r) >> 1;
                INT t = mid;
                if (t * _y <= left)
                    l = mid + 1;
                else r = mid;
            }
            re.num[i] = r - 1;
            INT t = r - 1;
            left = left - (t * _y);
        }
        while (re.num[re.len] == 0 && re.len) re.len--;
        return re;
    }
    inline friend INT operator %(const INT &x,const INT &y) {
        if ((!y.len && !y.num[0]) || (!x.len && !x.num[0])) { return INT(); }
        INT left,_y = abs(y);
        left.sign = (x.sign && !y.sign);
        left.len = -1;
        for (int i = x.len; i >= 0; i--) {
            memmove(left.num + 1,mid;
            while (l < r) {
                mid = (l + r) >> 1;
                INT t = mid;
                if (t * _y <= left)
                    l = mid + 1;
                else r = mid;
            }
            INT t = r - 1;
            left = left - (t * _y);
        }
        return left;
    }
    inline friend INT shr(const INT &x) {
        INT re;
        re.len = x.len;
        for (int i = re.len; i >= 0; i--) {
            if (x.num[i] & 1 && i - 1 >= 0)
                re.num[i - 1] += MOD >> 1;
            re.num[i] += x.num[i] >> 1;
        }
        if (re.len && !re.num[re.len]) re.len--;
        return re;
    }
    INT &operator +=(const INT &x) { return *this = *this + x; }
    INT &operator -=(const INT &x) { return *this = *this - x; }
    INT &operator *=(const INT &x) { return *this = *this * x; }
    INT &operator /=(const INT &x) { return *this = *this / x; }
    INT &operator %=(const INT &x) { return *this = *this % x; }
};

int gcd(int a,int b) {
    return b == 0 ? a : gcd(b,a%b);
}

void get_prime(int k) {
    int i = 2;
    while (k>1) {
        if (k%i==0) {
            int sum = 0;
            while (k%i == 0) {
                sum++;
                k /= i;
            }
            G[i] = max(G[i],sum);
        }
        i++;
    }
}

int main() {
    //ios_base::sync_with_stdio(false); cin.tie(0);
    int n;
    ll i;
    while(~scanf("%d",&n)) {
        f(i,1,n)
            scanf("%d",&a[i]);
        m0(G);

        int d = 0;
        f(i,2,n) {
            int b = a[1] * a[i];
            int c = abs(a[1] - a[i]) << 1;
            int t = gcd(b,c);
            b /= t; c /= t;
            d = gcd(c,d);
            get_prime(b);
        }
        INT ans = 1LL;
        f(i,SIZE)
            while (G[i]--) {
                ans *= i;
            }
        ans.print();
        printf(" %d\n",d);

    }
    return 0;
}