Faulhaber's Triangle（分子分母的计算）

题意：给出这样一个计算方法，除了第一列以外的数，计算方法是该位置乘以左上角的值，举个例子：比如第三行第二列的是3/2×1/6=1/4(行是分子，列是分母)。第一列的是这一行的所有除第一列的值加和，用一去减去和：比如第二行1-（1/2+1/3）=1/6。问第n行第m列是多少。

注意：输出格式要特判一下。

AC代码：

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <deque>
#include <stack>
using namespace std;
typedef long long ll;
const int MAX=3e7+7;
deque <ll> dq;
typedef long long LL;
struct AA
{
    LL x;
    LL y;
} a[450][450];
void f()
{
    memset(a,0,sizeof(a));
    LL L,R,m,i,j;
    a[0][1].x=1;
    a[0][1].y=1;
    a[1][1].x=1;
    a[1][1].y=2;
    a[1][2].x=1;
    a[1][2].y=2;
    for(i=2; i<=410; i++)
    {
        R=1;
        for(j=2; j<=i+1; j++)
        {
            LL f=i*a[i-1][j-1].x;
            LL g=j*a[i-1][j-1].y;
            if(f==0||g==0)
            {
                a[i][j].x=0;
                a[i][j].y=0;
                continue;
            }
            //约分
            LL gg=__gcd(f,g);
            a[i][j].x=f/gg;
            a[i][j].y=g/gg;
            if(a[i][j].y!=0&&a[i][j].x!=0)//求除第一列之外的分母的最小公倍数
            {
                R=a[i][j].y/__gcd(a[i][j].y,R)*R;
            }
        }
        LL ans=0;
        for(j=2;j<=i+1;j++)//求除第一列之外分子的和
        {
            if(a[i][j].x!=0&&a[i][j].y!=0)
                ans+=a[i][j].x*(R/a[i][j].y);
        }
        L=R-ans;//和的分子
        if(L==0)
        {
            a[i][j].x=0;
            a[i][j].y=0;
            continue;
        }
        //约分
        m=__gcd(R,L);
        a[i][1].x=L/m;
        a[i][1].y=R/m;
    }
}
int main()
{
    LL x,n,T,e,m;
    cin>>T;
    f();
    while(T--)
    {
        cin>>e>>n>>m;
        if(a[n][m].x==0)
            cout<<e<<" 0"<<endl;
        else
        if(a[n][m].x==a[n][m].y)
            cout<<e<<" 1"<<endl;
        else
        if(a[n][m].y==1)
             cout<<e<<" "<<a[n][m].x<<endl;
        else
        if(a[n][m].y<0&&a[n][m].x>0)
        {
            cout<<e<<" "<<-a[n][m].x<<"/"<<-a[n][m].y<<endl;
        }
        else
           cout<<e<<" "<<a[n][m].x<<"/"<<a[n][m].y<<endl;
    }
}