【藍橋杯】BASIC-30 階乘計算

• 2019 年 11 月 13 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/102981773

題目描述：

輸入一個正整數n，輸出n!的值。 其中n!=1*2*3*…*n。 演算法描述 n!可能很大，而電腦能表示的整數範圍有限，需要使用高精度計算的方法。使用一個數組A來表示一個大整數a，A[0]表示a的個位，A[1]表示a的十位，依次類推。 將a乘以一個整數k變為將數組A的每一個元素都乘以k，請注意處理相應的進位。 首先將a設為1，然後乘2，乘3，當乘到n時，即得到了n!的值。

輸入描述：

輸入包含一個正整數n（n< =1000）。

輸出描述：

輸出n!的準確值。

輸入樣例：

10 

輸出樣例：

3628800

解題思路：

藍橋杯的數據就nm大得離譜，我太難了，一開始我傻比地把maxn設成了1001，一提交就出現WA，只過了27%的測試用例。當輸入為1000時，輸出結果有2567位，然後我把maxn改成了3001。沒必要開太大，不然刪除前置0的時候會多耗時。

AC程式碼：

#include <bits/stdc++.h>  using namespace std;  #define Up(i,a,b) for(int i = a; i <= b; i++)  const int maxn = 10001;    int main()  {      ios::sync_with_stdio(false);      cin.tie(0),cout.tie(0);      int a[maxn] = {1};      int n;      cin >> n;      Up(i,1,n)      {          Up(j,0,maxn-1)          {              a[j] *= i;          }          Up(j,0,maxn-1)          {              if(a[j] >= 9)              {                  a[j+1] += a[j]/10;                  a[j] %= 10;              }          }      }      int i = maxn-1;      while(i>0 && a[i]==0)   //刪除前置0      {          i--;      }      for( ; i >= 0; i--)      {          cout << a[i];      }      return 0;  }