The basic approach looks sensible, but I do have a few suggestions for improvements.

using namespace std;

Bad idea. It may be a nuisance having to prepend std:: everywhere, but it's a short name in order to reduce the nuisance, and the things which could go wrong are quite bad.

void add_base_and_power(Prime_factorization& prime_factorization, int    base, int power)

What happened to the whitespace in int base? A single space suffices.

What do the names communicate and fail to communicate? The name prime_factorization communicates nothing: the type already says that. What purpose does this particular prime factorisation serve? The name base doesn't really fit the context IMO: you're not accumulating to a Base_power_pairs. add_prime_power(Prime_factorization accumulator, int prime, int power) would make it crystal clear what the function does.

void check_if_is_factor(Prime_factorization& prime_factorization, int &number, int divisor)

Again, names.

    if (number % divisor == 0) { // If the divisor is a base, we divide until it no longer can

This isn't wrong, but I wonder whether you made a conscious choice between this approach and

    int power { 0 };
    while (number % divisor == 0) {
        number /= divisor;
        ++power;
    }

    if (power > 0)
    {
        // Add base and power to factorization
        add_base_and_power(prime_factorization, divisor, power);
    }

I find the latter more aesthetically pleasing. It doesn't do a test which it knows will succeed.

NB this point is purely a subjective point about style - I'm not trying to microoptimise, and microoptimisations should be done with good benchmarks.

void decompose(Prime_factorization& prime_factorization, int number)

What is being decomposed here? My instinct would be that the first argument is the most relevant to interpreting the function name, but that doesn't make sense in this case.

    for (int div { 3 }; div * div <= number && number > 1; div += 2)

I've seen you use this int name { val } a few times, and (not being a C++ user) I'm not familiar with it. Does it have some advantage over int name = val to counter the disadvantage of requiring more effort to port to a different language?

There's a case to be made for calculating the square root of number outside the loop: firstly on micro-optimisation grounds, but secondly on correctness grounds. div * div could overflow the type.

    // We must print the base-power combinations in sorted order
    sort(prime_factorization.begin(), prime_factorization.end(), [](pair<int, int> p1, pair<int, int> p2) { return p1.first < p2.first; });

    if (okay) {
        cout << 1 << '\n';

        for (auto& i : prime_factorization)
            cout << i.first << ' ' << (i.second / m) << '\n';
    } else
        cout << 0;

Two things here: firstly, since the sorted values are only needed in one branch of the if it makes more sense to push the sort into that branch. Secondly,

if (test) {
    foo;
} else
    bar;

is easily the weirdest bracing style I've ever seen, and weird style is not good for collaboration. Do you use a company or published style guide?

Finally, my one algorithmic observation.

    // Check if we've already got the base we're trying to add
    auto it = find_if(prime_factorization.begin(), prime_factorization.end(), [&](pair <int, int> p) { return p.first == base; } );

    if (it != prime_factorization.end()) // If yes, add the power to the existing base
        it->second += power;
    else
        prime_factorization.push_back(make_pair(base, power)); // Else, create a new base

Linear search is never ideal. If you're using a recent standard, std::unordered_map is asymptotically preferable, and also IMO conveys the purpose better. Or maybe you would be better off with sort::map, which would remove the need to sort at the end.