noip1998 高精度計算 （高精度）

A1115. 高精度計算

1.0s   記憶體限制：

256.0MB  

​​653​​   AC次數：

250   平均分：

51.49

将本題分享到：

​​檢視未格式化的試題​​​   

​​​送出​​​   

​​​試題讨論​​

試題來源

　　NOIP1998 普及組

問題描述

　　用高精度計算出S=1！+2！+3！+…+n！（n≤50）

　　其中“！”表示階乘，例如：5！=5*4*3*2*1。

　　輸入正整數N，輸出計算結果S。

輸入格式

　　輸入包含一個整數N（N<=50）

輸出格式

　　輸出為一個整數，為計算結果S。

解析：高精度。

代碼：

#include<cstdio>
#include<algorithm>
using namespace std;

const long long len=1e8;
const int maxn=200;
long long a[maxn],b[maxn];

void multip(int x)
{
  long long i,last=0;
  for(i=1;i<=b[0];i++)
    {
      b[i]=b[i]*x+last;
      last=b[i]/len,b[i]%=len;
  }
  if(last>0)b[++b[0]]=last;
}

void add()
{
  long long i,k,last=0;
  k=min(a[0],b[0]);
  for(i=1;i<=a[0];i++)
    {
      a[i]=a[i]+b[i]+last;
      last=a[i]/len,a[i]%=len;
  }
  for(i=k+1;i<=b[0];i++)
    a[i]=b[i]+last,last=a[i]/len,a[i]%=len;
  for(i=k+1;i<=a[0] && last>0;i++)
    a[i]+=last,last=a[i]/len,a[i]%=len;
  a[0]=max(a[0],b[0]);
  if(last>0)a[++a[0]]=last;
}

int main()
{
  int i,n;
  scanf("%d",&n);
  a[0]=a[1]=b[0]=b[1]=1;
  for(i=2;i<=n;i++)multip(i),add();
  
  printf("%I64d",a[a[0]]);
  for(i=a[0]-1;i>=1;i--)printf("%08I64d",a[i]);
  return 0;
}