fork(6) download
  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
stdin
Standard input is empty
stdout
Catalan(9913) modulo 1000000000007 = 944953891838