洛谷 1291 [SHOI2002]百事世界杯之旅

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll N=35;
ll n,a[N],b[N];
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll solve(ll a)
{
    ll ret=0;while(a)ret++,a/=10;return ret;
}
int main()
{
    scanf("%lld",&n);
    a[n-1]=n;b[n-1]=1;
    for(ll i=n-2;i>=0;i--)
    {
        b[i]=b[i+1]*(n-i);
        a[i]=a[i+1]*(n-i)+n*b[i+1];
        ll d=gcd(a[i],b[i]);
        a[i]/=d;b[i]/=d;
    }
    ll c=a[0]/b[0];a[0]%=b[0];
    if(!a[0])
    {
        printf("%lld",c);return 0;
    }
    ll k=solve(c);
    for(ll i=1;i<=k;i++)printf(" ");printf("%lld\n",a[0]);
    ll d=solve(b[0]);
    if(c)printf("%lld",c);
    for(ll i=1;i<=d;i++)printf("-");printf("\n");
    for(ll i=1;i<=k;i++)printf(" ");printf("%lld",b[0]);
    return 0;
}