Необходимо вычислить энное число Каталана. Посчитал числитель и знаменатель, а поделить не могу. прошу помощи. Или хоть на яве с BigInteger решение...
#include <vector>
#include <iostream>
using namespace std;
int main(int argc, char *argv[])
{
const int base = 1000*1000*1000;
vector <int> a, b;
int n, carry = 0;
cin>>n;
a.push_back(n); //числитель считаем от n+2 до 2*n
for (int ii=n+2; ii!=(2*n)+1;++ii) { //т.о. мы сразу поделили на n+1 (первый множитель чисел каталана)
carry = 0; //и на n (из знаменателя)
for (size_t i=0; i<a.size() || carry; ++i) {
if (i == a.size())
a.push_back (0);
long long cur = carry + a[i] * 1ll * ii;
a[i] = int (cur % base);
carry = int (cur / base);
}
}
while (a.size() > 1 && a.back() == 0) a.pop_back();
b.push_back(n); //знаменатель считаем от 1 до n
for (int ii=1; ii!=n+1;++ii) { //т.к. один из n! сократился со знаменателем
carry = 0;
for (size_t i=0; i<b.size() || carry; ++i) {
if (i == b.size())
b.push_back (0);
long long cur = carry + b[i] * 1ll * ii;
b[i] = int (cur % base);
carry = int (cur / base);
}
}
while (b.size() > 1 && b.back() == 0) b.pop_back();
cout<<(a.empty() ? 0 : a.back());
for (int i=(int)a.size()-2; i>=0; --i) cout<<(a[i]);
cout<<" ";
cout<<(b.empty() ? 0 : b.back());
for (int i=(int)b.size()-2; i>=0; --i) cout<<(b[i]);
//system("PAUSE");
cout<<endl;
return 0;
}
.