На С++ представляем число просто в виде vector<unsigned int>
и расписываем длинную арифметику. Поскольку прямая рекурсия в этом случае убьет любые надежды даже при обычной арифметике, применяем мемоизацию.
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
using ullong = unsigned long long int;
class tooLong
{
public:
static const unsigned int magic = 1000000000, digs = 9;
tooLong(unsigned int n = 0)
{
while(n)
{
a.push_back(n % tooLong::magic);
n /= tooLong::magic;
}
if (a.empty()) a.push_back(0);
};
friend tooLong operator *(const tooLong& a, const tooLong& b);
friend ostream& operator <<(ostream&os, const tooLong& a);
bool operator !() const { return !(a.size() == 1 && a[0] == 0); }
private:
vector<unsigned int> a;
static vector<unsigned int> sum(const vector<unsigned int>& a, const vector<unsigned int>& b,
unsigned int shift_b = 0);
static vector<unsigned int> mul(const vector<unsigned int>& a, unsigned int b);
};
vector<unsigned int> tooLong::sum(const vector<unsigned int>& a, const vector<unsigned int>& b,
unsigned int shift_b)
{
size_t sz = max(a.size(),b.size()+shift_b);
vector<unsigned int> r(sz);
unsigned int c = 0;
for(unsigned int i = 0; i < sz; ++i)
{
r[i] = (i < a.size() ? a[i] : 0) +
(i < shift_b ? 0 : i < b.size()+shift_b ? b[i-shift_b] : 0)
+ c;
c = r[i] / tooLong::magic;
r[i] %= tooLong::magic;
}
if (c) r.push_back(c);
return r;
}
vector<unsigned int> tooLong::mul(const vector<unsigned int>& a, unsigned int b)
{
vector<unsigned int> r;
ullong c = 0;
for(int i = 0; i < a.size(); ++i)
{
ullong s = ullong(a[i]) * ullong(b) + c;
c = s / magic;
s %= magic;
r.push_back((unsigned int)s);
}
while(c)
{
r.push_back(c % magic);
c /= magic;
}
return r;
}
tooLong operator *(const tooLong& aa, const tooLong& bb)
{
vector<unsigned int> r;
const vector<unsigned int>& a = (aa.a.size() > bb.a.size()) ? bb.a : aa.a;
const vector<unsigned int>& b = (aa.a.size() > bb.a.size()) ? aa.a : bb.a;
for(int i = 0; i < a.size(); ++i)
{
vector<unsigned int> s = tooLong::mul(b,a[i]);
r = tooLong::sum(r,s,i);
}
tooLong res;
res.a = r;
return res;
}
ostream& operator <<(ostream&os, const tooLong& a)
{
os << a.a[a.a.size()-1];
os << setfill('0');
for(int i = (int)a.a.size()-2; i >= 0; --i)
os << setw(tooLong::digs) << a.a[i];
return os;
}
tooLong F(int N)
{
static tooLong L[21] = {0};
if ( !L[N] ) return L[N];
tooLong R = 1;
if (N == 1) return R;
for(int m = 1; m < N; ++m)
R = R*F(m);
L[N] = R*N;
return L[N];
}
int main()
{
int N;
cin >> N;
cout << F(N);
}
Если хочется посмотреть, как выглядит F(19)
- без проблем: https://ideone.com/iWM549 - для 20 результат слишком большой, не показывает. Тест https://ipc.susu.ru/5344-5.html код проходит без проблем.
P.S. Интересно, что вариант MBo работает немного дольше (понятно, не в смысле питоновский файл :), а измененный алгоритм расчета на С++)...
system("pause");