洛谷 p1625

高精度

我以为这题必有高论，怎么想也想不出来，没想到竟是如此粗鄙做法。

我们写一个高精度模拟一下，然后枚举约数看是否能约分，由于我不会高精度除法，就抄了一发

其实这种两项之比和项数有关的数列是不能推通项的，只能暴力模拟

#include<bits/stdc++.h>
using namespace std;
const int N = 2010;
int n, m;
struct Bigint {
    int a[N], len;
    Bigint friend operator + (Bigint &A, Bigint &B)
    {
        Bigint C;
        memset(C.a, 0, sizeof(C.a));
        int lim = max(A.len, B.len);
        for(int i = 1; i <= lim; ++i)
        {
            C.a[i] += A.a[i] + B.a[i];
            C.a[i + 1] += C.a[i] / 10;
            C.a[i] %= 10;
        }
        C.len = lim;
        if(C.a[lim + 1]) ++C.len;
        return C;
    } 
    Bigint friend operator * (Bigint A, int x)
    {
        for(int i = 1; i <= A.len; ++i) A.a[i] *= x;
        for(int i = 1; i <= A.len; ++i) 
        {
            A.a[i + 1] += A.a[i] / 10;
            A.a[i] %= 10;
        }
        while(A.a[A.len + 1] >= 10)
        {
            ++A.len;
            A.a[A.len + 1] += A.a[A.len] / 10;
            A.a[A.len] %= 10; 
        }
        if(A.a[A.len + 1] > 0) ++A.len;
        return A;
    }    
    Bigint friend operator / (Bigint &A, int x)
    {
        Bigint B;
        int tot = 0;
        memset(B.a, 0, sizeof(B.a));
        for(int i = A.len; i; --i)
        {
            tot = tot * 10 + A.a[i];
            B.a[i] = tot / x;
            tot %= x;
        }
        B.len = A.len;
        while(B.a[B.len] == 0) --B.len;
        return B;
    }
    void print()
    {
        for(int i = len; i; --i) printf("%d", a[i]);
        puts(""); 
    }
} down, up, base;
bool can_div(Bigint &A, int x)
{
    int tot = 0;
    for(int i = A.len; i; --i) tot = (tot * 10 + A.a[i]) % x;
    return (tot == 0);
}
int main()
{
    scanf("%d%d", &n, &m);
    down.len = 1;
    down.a[1] = 1;
    base.len = 1;
    base.a[1] = 1;
    for(int i = m + 1; i < n + m; ++i) base = base * i;
    for(int i = 1; i <= n; ++i)
    {
        up = up + base;
        base = base * i;
        base = base / (m + i);
    }
    for(int i = 2; i < n + m; ++i)
    {
        if(can_div(up, i)) up = up / i;
        else down = down * i;
    }
    for(int i = 2; i < n + m; ++i) if(can_div(up, i) && can_div(down, i)) 
    {
        up = up / i;
        down = down / i;
    }
    up.print();
    down.print();
    return 0;
}