Задачу по-видимому придется решать в лоб, т.е. через длинную арифметику. Если все делать "руками", то это сразу приводит к дилемме:
Реализовывать длинное число в виде массива десятичных цифр, что сделает вычисление финальной суммы тривиальной операцией, но существенно удлинит и замедлит процесс длинного умножения.
Реализовывать длинное число в виде массива цифр в системе счисления с основанием 2n/2, где n
- это ширина самого широкого умножения, поддерживаемого данной С++ платформой. Это ускорит длинное умножение, но потребует реализации длинного деления на 10
для того, чтобы получить цифры для сложения в финале.
Меня больше привлекает именно второй вариант. Например, (не гоняясь за процессорными тактами в операциях умножения и деления)
#include <cstdint>
#include <vector>
#include <algorithm>
#include <iostream>
using TDigit = std::uint32_t;
using TDigit2 = std::uint64_t;
const std::size_t BITS = std::numeric_limits<TDigit>::digits;
const TDigit2 BASE = (TDigit2) 1 << BITS;
using TNumber = std::vector<TDigit>;
void mul(TNumber &v, TDigit m)
{
if (m == 1)
return;
TDigit carry = 0;
for (TDigit &digit : v)
{
TDigit2 product = (TDigit2) digit * m + carry;
digit = product % BASE;
carry = (TDigit) (product / BASE);
}
if (carry > 0)
v.push_back(carry);
}
unsigned div10(TNumber &v)
{
TDigit r = 0;
for (std::size_t n = v.size(); n > 0; --n)
{
TDigit2 dd = (TDigit2) r * BASE + v.back();
std::copy_backward(v.begin(), v.end() - 1, v.end());
v.front() = (TDigit) (dd / 10);
r = dd % 10;
}
while (!v.empty() && v.back() == 0)
v.pop_back();
return r;
}
unsigned factorial_sum(unsigned n)
{
TNumber v = { 1 };
for (unsigned i = 1; i <= n; ++i)
{
unsigned m = i;
for (; m % 10 == 0; m /= 10);
mul(v, m);
}
unsigned sum = 0;
for (; !v.empty(); sum += div10(v));
return sum;
}
int main()
{
std::cout << "100! -> " << factorial_sum(100) << std::endl;
std::cout << "1000! -> " << factorial_sum(1000) << std::endl;
}
http://coliru.stacked-crooked.com/a/69d4651879a8fad5
Пользуясь идей, предложенной @Германом Борисовым в комментариях, можно получить эффективный компромисс между этими двумя подходами: используем систему счисления с основанием 10n, где n
выбирается максимально возможным так, чтобы перемножение двух цифр не приводило к переполнению на данной С++ платформе.
При этом функция умножения останется почти неизменной, а функция вычисления суммы цифр существенно упростится (полноценная функция деления станет ненужной)
#include <cstdint>
#include <vector>
#include <iostream>
using TDigit = std::uint32_t;
using TDigit2 = std::uint64_t;
const TDigit2 BASE = 1000000000u;
using TNumber = std::vector<TDigit>;
void mul(TNumber &v, TDigit m)
{
if (m == 1)
return;
TDigit carry = 0;
for (TDigit &digit : v)
{
TDigit2 product = (TDigit2) digit * m + carry;
digit = product % BASE;
carry = (TDigit) (product / BASE);
}
for (; carry > 0; carry /= BASE)
v.push_back(carry % BASE);
}
unsigned factorial_sum(unsigned n)
{
TNumber v = { 1 };
for (unsigned i = 1; i <= n; ++i)
{
unsigned m = i;
for (; m % 10 == 0; m /= 10);
mul(v, m);
}
unsigned sum = 0;
for (TDigit d : v)
for (; d > 0; d /= 10)
sum += d % 10;
return sum;
}
int main()
{
std::cout << "100! -> " << factorial_sum(100) << std::endl;
std::cout << "1000! -> " << factorial_sum(1000) << std::endl;
}
http://coliru.stacked-crooked.com/a/68096eb9ebbb061f
Эксперимент на QuickBench показывает, что это - существенно более эффективный подход
http://quick-bench.com/G-XjO_3VniIvFLX2RWI3cuQLNTM
Разумеется, первый вариант не настолько эффективен, насколько он мог бы быть - из-за неэффективной реализации операции деления. Однако цели оптимизации и не ставилось. Все варианты работают за более чем приемлемое время.