Project Euler 题解 #20 Factorial digit sum

n! means n (n 1) ... 3 2 1

For example, 10! = 10 9 ... 3 2 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

//https://projecteuler.net/problem=20
//Factorial digit sum
#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
#define  MAX_LEN  1024 //数字串的最大长度
//该函数不能交换同一个地址上的值, 否则, 会将a b置0
template <class T> void Swap(T& a, T& b) 
{
if (&a == &b)
{
return;
}
a ^= b ^= a ^= b;
}
void MUL(char str1[], char str2[], char result[])
{
int len1 = strlen(str1), len2 = strlen(str2);
int index = 0, carry = 0, temp = 0;;
for (int i1 = len1 - 1; i1 >= 0; --i1)
{
index = len1 - 1 - i1;
for (int i2 = len2 - 1; i2 >= 0; --i2)
{
temp = (result[index] - '0') + (str1[i1] - '0') * (str2[i2] - '0') + carry;
result[index] = temp%10 + '0';
carry = temp/10;
++index;
}
if (carry > 0)
{
result[index] = (result[index] - '0') + carry + '0';
carry = 0;
++index;
}
}
//去掉结果数字串中前面的0
while (result[index] == '0' && index > 0)
{
--index;
}
result[++index] = '\0';
int i =0, j = index - 1;
while(i < j)
{
Swap(result[i], result[j]);
++i;
--j;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int N = 100;
char product[MAX_LEN] = "1";
for (int i = 1; i <= N; ++i)
{
char mult[MAX_LEN] = {0};
sprintf_s(mult, MAX_LEN, "%d", i);
char result[MAX_LEN];
memset(result, '0', MAX_LEN);
MUL(product, mult, result);
memcpy_s(product, MAX_LEN, result, MAX_LEN);
}
int sum = 0;
for (int i = 0; i < strlen(product); ++i)
{
cout<<product[i];
sum += product[i] - '0';
}
cout<<endl;
cout<<"sum = "<<sum<<endl;
system("pause");
return 0;
}