洛谷題解P1009 階乘之和

摘要： 實現程式碼： #include<iostream> using namespace std; int a[2000]; int c[2000]; const int maxDigit=1000; //最大位數，除錯時可設n=4,maxDigit=3 // 階乘相加 void...

實現程式碼：

#include<iostream>
using namespace std;

int a[2000];
int c[2000];
const int maxDigit=1000; //最大位數，除錯時可設n=4,maxDigit=3

// 階乘相加
void add(int *a,int *c)
{
int carry = 0;
// 比如1!+2!+3!+4!
// i=1時，c[1]=1!=1
// i=2時，c[1]=1+2!=3
// i=3時，c[1]=3+3!=9
// i=4時，c[1]=9+4=13,carry=1,c[1]=3,c[2]=c[2]+a[2]+carry=0+2+1=3
for(int i = 1; i <= maxDigit; i++)
{
c[i] += (a[i] + carry);
carry = c[i]/10;
c[i] %= 10;
}
}

//求階乘
void fact(int *a,int num)
{
int carry = 0; // 進位
for(int i=1; i <= maxDigit; i++)
{
// 從高位往低位儲存資料，比如5!=120,則a[4]=a[5]=...=0,a[3]=1,a[2]=2,a[1]=0
a[i] = a[i] * num + carry;
carry = a[i] / 10;
a[i] %= 10;
}
}

int main()
{
int n;
cin >> n;
a[1] = 1;
for(int i=1;i<=n;i++)
{
fact(a, i);
add(a, c);
}

bool flag = false; // 當碰到第一個非0時，更新為true
for(int i = 1000; i >= 1; i--)
{
// 左邊的0不要打印出來，從第一個非0數字開始列印
// 比如000……000120，打印出120
if(c[i] != 0)
{
flag = true;
}

if(flag)
{
cout << c[i];
}
}

return 0;
}