How to calculate N factorial for very big numbers?

Question

I was solving a practice problem for a competition and I got this output in my test script. I was supposed to calculate this 37 digit number (84 bits) and I don't know how this would be possible in C++. Any ideas?

----------------------------------------------------------------------------------------------------

Exercise #8: Failure                                                                                

Expected answer:                                  Your answer:                                      
2982946161059046714576278832998350000             18446744073709501616                              

----------------------------------------------------------------------------------------------------

Here is my code. Only the part where C is 2 is executed. In my problem, where L is the length of the given string, I need to calculate L! / <occuranceOfA> / <occuranceOfB> * ... * <occuranceOfZ> (excluding the occurances that are equal to 0)

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <string.h>

static std::string A[110000];
unsigned long long C;

unsigned long long factorial(unsigned long long n) {
  if (n == 1) return 1;
  else return n * factorial(n - 1);
}

void solve(std::string filename) {

  std::ifstream fin(filename + ".in");
  std::ofstream fout(filename + ".out");
  std::cout << filename << std::endl;

  unsigned long long c = 0;
  fin >> C;
  while (fin >> A[c]) c++;
  if (C == 1) {
    for (unsigned long long i=0; i<c-1; i++) {
      std::next_permutation(A[i].begin(), A[i].end());
      if (A[i] != A[i+1]) {
        fout << A[i];
        return;
      }
    }
  } else {
    unsigned long long result = factorial(A[0].length()), arr[26];
    memset(arr, 0, 26*sizeof(*arr));
    for (unsigned long long i=0; i<A[0].length(); i++) {
      char c = A[0].at(i);
      if ((int)c >= 97 && (int)c <= 122)
        arr[(int)c - 97] += 1;
    }
    for (unsigned long long i=0; i<26; i++)
      if (arr[i] != 0)
        result /= factorial(arr[i]);
    result -= c;
    fout << result;
    return;
  }
}

It would be better if you could show us your code, it would make it easier to help. — ShadowMitia, Mar 12 '21 at 21:53
https://stackoverflow.com/questions/12988099/big-numbers-library-in-c , but I'm guessing for a competition you'd have to roll your own implementation? — yano, Mar 12 '21 at 21:54
You can use an approximation formula: https://en.wikipedia.org/wiki/Factorial#Rate_of_growth_and_approximations_for_large_n — Christian Vincenzo Traina, Mar 12 '21 at 22:04

score 0 · Answer 1 · answered Mar 12 '21 at 22:09

0

you answer is here

#include<iostream>
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;
using namespace std;
cpp_int large_fact(int num) {
   cpp_int fact = 1;
   for (int i=num; i>1; --i)
      fact *= i;
   return fact;
}
int main() {
   cout << "Factorial of 50: " << large_fact(50) << endl;
}

Factorial of 50:
30414093201713378043612608166064768844377641568960512000000000000

answered Mar 12 '21 at 22:09

kzlca

391
1
6

**Your** answer should contain **your** efforts. Also, the possibility says that the OP might not have the Boost library. – Rohan Bari Mar 12 '21 at 22:59

How to calculate N factorial for very big numbers?

1 Answers1