pepsi.cpp

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

#include <iostream.h>
#include <fstream.h>
#include <string.h>

ifstream in("pepsi.in");
ofstream out("pepsi.out");
//#define out cout

#define LEN  100
typedef int bignum[LEN];

bignum a,b;
int n;

void init(int *a,int x)
{
  memset(a,0,sizeof(int)*LEN);
  a[0]=1;
  a[1]=x;
}

void mul(int *a,int x)
{
  int i ,g ,s;
  int l = a[0];
  g = 0;
  for (i=1;i<=l;i++)
  {
    s = a[i]*x+g;
    a[i]=s % 10;
    g = s/10;
  }
  for (;g>0;)
  {
    a[++l]=g%10;
    g/=10;
  }
  a[0]=l;
}

void add(int *a,int *b)
{
  int i ,g ,s,l;
  if (a[0]>b[0]) l = a[0]; else l = b[0];
  g = 0;
  for (i=1;i<=l;i++)
  {
    s = a[i]+b[i]+g;
    a[i]=s%10;
    g=s/10;
  }
  for (;g>0;)
  {
    a[++l]=g%10;
    g/=10;
  }
  a[0]=l;
}

void sub(int *a,int *b)
{
  int i, g,s,l;
  l=a[0];
  g = 0;
  for (i=1;i<=l;i++)
  {
    s = a[i]-b[i]-g;
    if (s<0) { g = 1;s+=10;} else g= 0;
    a[i]=s;
  }
  while (l>1 && a[l]==0) l--;
  a[0]=l;
}

int bigger(int *a,int *b)
{
   if (a[0]>b[0]) return 1;
   if (a[0]<b[0]) return 0;
   for (int i=a[0];i>0;i--)
    if (a[i] > b[i]) return 1;
    else if (a[i] < b[i]) return 0;

   return 1;
}

void div10(int *a)
{
  int i , l =a[0];
  for (i=1;i<l;i++)
   a[i]=a[i+1];
  a[l]=0;
  a[0]=l-1;
}

void mul10(int *a)
{
  int i , l =a[0];
  for (i=l;i>0;i--)
   a[i+1]=a[i];
  a[1]=0;
  a[0]=l+1;
}

void div(int *a,bignum b,int *c)
{
   init(c,0);
   int mv = 1;
   while (bigger(a,b))
    {
      mul10(b);
      mv++;
    }
   for (;mv >0;mv--)
   {
     while (bigger(a,b))
      {
         c[mv]++;
         sub(a,b);
      }
     if (mv > 1)
     div10(b);
   }

   int i = LEN-1;
   while (i>1 && c[i]==0) i--;
   c[0]=i;
   i = LEN-1;
   while (i>1 && a[i]==0) i--;
   a[0]=i;
}

int zero(int *a)
{
  return (a[0]==1 && a[1]==0);
}

void outp(int *a)
{
  for (int i = a[0]; i>0; i--)
   out<<a[i];
}

void copy(int *a,int *b)
{
  for (int i = 0;i<LEN;i++)
   a[i] = b[i];
}


void gcd(bignum a, bignum b,bignum &c)
{
  div(b,a,c);
  if (zero(b)) copy(c,a);
  else
   {
     gcd(b,a,c);
   }
}

int main()
{
  in>>n;

  init(a,0);
  for (int i =1;i<=n;i++)
  {
    init(b,n);
    for (int j =1;j<=n;j++)
     if (i!=j) mul(b,j);

    add(a,b);
  }

  bignum c;
  init(b,1);
  for (int i =1;i<=n;i++) mul(b,i);
  bignum aa , bb ;

  div(a,b,c);
  if (zero(a))
   {
      outp(c);
      out<<endl;
   }
  else
    {
       bignum cc;
       copy(aa,a);
       copy(bb,b);
       gcd(a,b,cc);
       div(aa,cc,a);
       div(bb,cc,b);
       int i;
       for (i=1;i<=c[0];i++) out<<' ';
       outp(a);
       out<<endl;
       outp(c);
       for (i=1;i<=b[0];i++) out<<'-';
       out<<endl;
       for (i=1;i<=c[0];i++) out<<' ';
       outp(b);
       out<<endl;
       
    }
  return 0;
}