language: C++ 4.7.2 (gcc-4.7.2)
date: 285 days 16 hours ago
link:
visibility: public 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <utility>
#include <vector>
 
std::vector< std::pair<int, int> > factor_table;
void fill_sieve( int n )
{
        factor_table.resize(n+1);
        for( int i = 1; i <= n; ++i )
                factor_table[i] = std::pair<int, int>(i, 1);
        for( int j = 2, j2 = 4; j2 <= n; (j2 += j), (j2 += ++j) ) {
                if (factor_table[j].second == 1) {
                        int i = j;
                        int ij = j2;
                        while (ij <= n) {
                                factor_table[ij] = std::pair<int, int>(j, i);
                                ++i;
                                ij += j;
                        }
                }
        }
}
 
std::vector<unsigned> powers;
 
template<int dir>
void factor( int num )
{
        while (num != 1) {
                powers[factor_table[num].first] += dir;
                num = factor_table[num].second;
        }
}
 
template<unsigned N>
void calc_combinations(unsigned (&bin_sizes)[N])
{
        using std::swap;
 
        powers.resize(0);
        if (N < 2) return;
 
        unsigned& largest = bin_sizes[0];
        size_t sum = largest;
        for( int bin = 1; bin < N; ++bin ) {
                unsigned& this_bin = bin_sizes[bin];
                sum += this_bin;
                if (this_bin > largest) swap(this_bin, largest);
        }
        fill_sieve(sum);
 
        powers.resize(sum+1);
        for( unsigned i = largest + 1; i <= sum; ++i ) factor<+1>(i);
        for( unsigned bin = 1; bin < N; ++bin )
                for( unsigned j = 2; j <= bin_sizes[bin]; ++j ) factor<-1>(j);
}
 
#include <iostream>
#include <cmath>
int main(void)
{
        unsigned bin_sizes[] = { 5, 15 };
        calc_combinations(bin_sizes);
        char* sep = "";
        for( unsigned i = 0; i < powers.size(); ++i ) {
                if (powers[i]) {
                        std::cout << sep << i;
                        sep = " * ";
                        if (powers[i] > 1)
                                std::cout << "**" << powers[i];
                }
        }
        std::cout << "\n\n";
}