fork(1) 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. template<unsigned N>
  35. void calc_combinations(unsigned (&bin_sizes)[N])
  36. {
  37. using std::swap;
  38.  
  39. powers.resize(0);
  40. if (N < 2) return;
  41.  
  42. unsigned& largest = bin_sizes[0];
  43. size_t sum = largest;
  44. for( int bin = 1; bin < N; ++bin ) {
  45. unsigned& this_bin = bin_sizes[bin];
  46. sum += this_bin;
  47. if (this_bin > largest) swap(this_bin, largest);
  48. }
  49. fill_sieve(sum);
  50.  
  51. powers.resize(sum+1);
  52. for( unsigned i = largest + 1; i <= sum; ++i ) factor<+1>(i);
  53. for( unsigned bin = 1; bin < N; ++bin )
  54. for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j);
  55. }
  56.  
  57. #include <iostream>
  58. #include <cmath>
  59. int main(void)
  60. {
  61. unsigned bin_sizes[] = { 8, 1, 18, 19, 10, 10, 7, 18, 7, 2, 16, 8, 5, 8, 2, 3, 19, 19, 12, 1, 5, 7, 16, 0, 1, 3, 13, 15, 13, 9, 11, 6, 15, 4, 14, 4, 7, 13, 16, 2, 19, 16, 10, 9, 9, 6, 10, 10, 16, 16 };
  62. calc_combinations(bin_sizes);
  63. char* sep = "";
  64. for( unsigned i = 0; i < powers.size(); ++i ) {
  65. if (powers[i]) {
  66. std::cout << sep << i;
  67. sep = " * ";
  68. if (powers[i] > 1)
  69. std::cout << "**" << powers[i];
  70. }
  71. }
  72. std::cout << "\n\n";
  73. }
  74.  
Success #stdin #stdout 0.02s 2860KB
stdin
Standard input is empty
stdout
2**93 * 3**61 * 5**41 * 7**29 * 11**28 * 13**21 * 17**23 * 19**22 * 23**21 * 29**16 * 31**15 * 37**13 * 41**11 * 43**11 * 47**10 * 53**9 * 59**8 * 61**8 * 67**7 * 71**6 * 73**6 * 79**6 * 83**5 * 89**5 * 97**5 * 101**4 * 103**4 * 107**4 * 109**4 * 113**4 * 127**3 * 131**3 * 137**3 * 139**3 * 149**3 * 151**3 * 157**3 * 163**2 * 167**2 * 173**2 * 179**2 * 181**2 * 191**2 * 193**2 * 197**2 * 199**2 * 211**2 * 223**2 * 227**2 * 229**2 * 233**2 * 239**2 * 241**2 * 251 * 257 * 263 * 269 * 271 * 277 * 281 * 283 * 293 * 307 * 311 * 313 * 317 * 331 * 337 * 347 * 349 * 353 * 359 * 367 * 373 * 379 * 383 * 389 * 397 * 401 * 409 * 419 * 421 * 431 * 433 * 439 * 443 * 449 * 457 * 461 * 463 * 467 * 479 * 487