fork(27) download
copy 
  1. #include <utility>
  2. #include <vector>
  3.  
  4. std::vector< std::pair<int, int> > factor_table;
  5. void fill_sieve( int n )
  6. {
  7. 	factor_table.resize(n+1);
  8. 	for( int i = 1; i <= n; ++i )
  9. 		factor_table[i] = std::pair<int, int>(i, 1);
  10. 	for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
  11. 		if (factor_table[j].second == 1) {
  12. 			int i = j;
  13. 			int ij = j2;
  14. 			while (ij <= n) {
  15. 				factor_table[ij] = std::pair<int, int>(j, i);
  16. 				++i;
  17. 				ij += j;
  18. 			}
  19. 		}
  20. 	}
  21. }
  22.  
  23. std::vector<unsigned> powers;
  24.  
  25. template<int dir>
  26. void factor( int num )
  27. {
  28. 	while (num != 1) {
  29. 		powers[factor_table[num].first] += dir;
  30. 		num = factor_table[num].second;
  31. 	}
  32. }
  33.  
  34. void calc_catalan(unsigned N)
  35. {
  36.     powers.resize(2*N+1);
  37.     for( unsigned k = 2; k <= N; ++k ) {
  38.          factor<+1>(k+N);
  39.          factor<-1>(k);
  40.     }
  41. }
  42.  
  43. #include <iostream>
  44. #include <cmath>
  45.     int main(void)
  46.     {
  47.         fill_sieve(20000);
  48.         unsigned N = 9913;
  49.         unsigned long long M = 1000000000007LL;
  50.         calc_catalan(N);
  51.         char* sep = "";
  52.         unsigned long long result = 1;
  53.         for( unsigned i = 0; i < powers.size(); ++i ) {
  54.             while (powers[i]--) {
  55.                 result *= i;
  56.                 result %= M;
  57.             }
  58.         }
  59.         std::cout << "Catalan(" << N << ") modulo " << M << " = " << result << "\n\n";
  60.     }
Success #stdin #stdout 0.02s 2860KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Catalan(9913) modulo 1000000000007 = 944953891838
https://ideone.com/FDWfB
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!