긴 숫자. 부서

Question

세계! 문제가 있습니다. 오늘 카탈로니아 어 번호를 찾는 코드를 만들려고했습니다. 하지만 내 프로그램에 긴 숫자가 될 수 있습니다. 나는 분자와 분모를 발견했다. 그러나 나는 긴 숫자를 나눌 수 없다! 또한 표준 라이브러리 만이이 프로그램에서 사용해야합니다. 도와주세요, 제발. 이것은 내 코드입니다

#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);      
    for (int ii=n+2; ii!=(2*n)+1;++ii) { 
     carry = 0;      
     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);     
    for (int ii=1; ii!=n+1;++ii) { 
     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; 
} 

P.S. 나쁜 영어로 죄송합니다. =)

Answer 1

(2n)을 계산할 필요가 없습니다! (2N)을 계산하기 위해/(N (N + 1)!))가 this link에 주어진 점화식 사용할 수 있기 때문에!

C (0) = 1
C (N) =를 (4n-2) C (n-1)/(n + 1)

이렇게하면 32 비트 산술을 사용하여 처음 15 개 항목을 얻을 수 있습니다. 또한 임의의 길이의 정수를 16 비트 정수로 곱셈 및 나눗셈을 사용하여 최대 16384 개의 항을 생성 할 수 있습니다. 이것은 일반적인 임의 정밀도 산술보다 훨씬 쉬우 며 숙제로 설정 될 수도 있습니다.

Answer 2

긴 숫자의 표현에서 구현을 나누는 것은 매우 어려울 것입니다. 그러나 사실입니다. 제 생각에는 가장 간단한 방법은 Long_division입니다.