PRSUMARR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: clear_spice_98
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Integer factorization

PROBLEM:

Given N, let R denote the number of arrays A such that:

  • 1 \le A_1 \le A_2 \le \ldots \le A_{|A|} \le N
  • A_1 + A_2 + \ldots + A_{|A|} = N
  • A_1 \times A_2 \times \ldots \times A_{|A|} = N

Compute \min(R, 3)

EXPLANATION:

We first need to understand what exactly is being counted by the arrays A.

We would like A_1 \times A_2 \times \ldots\times A_{|A|} = N.
This in particular means that each A_i must be a factor of N.

Further, if A_i = 1 for some i, the product is unchanged; so in terms of the product we only need to care about the elements that are \gt 1.
So, for now let’s just assume that every A_i is \gt 1.
If we need 1's later, we can add them in without affecting the product.

Now, given that we’re working with elements that are \gt 1, the product always grows faster than the sum.
That is, if x, y \ge 2, then (x+y) \le xy.

So, as long as A_i \gt 1 for every i, we’ll definitely have

A_1 + A_2 + \ldots + A_{|A|} \le A_1 \times A_2 \times\ldots\times A_{|A|}

In particular, if the product equals N, the sum cannot exceed N.

This is helpful, because as we saw earlier, including copies of 1 doesn’t change the product at all.
On the other hand, each copy of 1 we include increases the sum by 1.

So, every time we have a product that equals N, we can simply take several copies of 1 and end up with an array whose sum also equals N.
In particular, observe that the number of ones we need to include is unique, given that all elements \gt 1 are fixed.

With the above observations, we can now see that the value R simply equals the number of ways of choosing integers \gt 1 such that their product equals N; because for each such choice, there’s a unique way to convert it to a valid array A by including copies of 1.

We only want to compute \min(R, 3), so let’s try to figure out when we have more than 3 possibilities.

Intuitively, when N has many factors, it is likely to have many combinations of them that work as products too.
So, it makes sense to instead look at numbers that have a small number of factors - which in turn means they must have a small number of prime factors too.

First, if N is a itself prime, there’s only one way to obtain N as a product of elements \gt 1; which is by taking N itself.
(N = 1 also has only a single array possible, that being [1]).

Next, suppose N has two prime factors, say N = pq where p \le q (note that we do allow p = q here).
Then, the only ways to obtain N as a product are via either [pq] or [p, q].
So, for these values of N, the answer is 2.

Next, suppose N has three prime factors, say N = pqr where p \le q\le r.
Then, we definitely have three different possible arrays: [pqr], [pq, r], [p, q, r].
There might be more possibilities, but we want \min(R, 3) so the answer here is just 3.

If N has \gt 3 prime factors, the value of \min(R, 3) is again just 3 since we’ll always be able to find three separate ways to write N as a product (one simple way is: let N = pqr where p and q are primes though r is not necessarily a prime; and then use the above construction.)

So, we have the following:

  • If N = 1 or N is a prime, the answer is 1.
  • If N has two prime factors, the answer is 2.
  • Otherwise, the answer is 3.

This only requires knowing the prime factors of N, which can be done in \mathcal{O}(\sqrt N).

TIME COMPLEXITY:

\mathcal{O}(\sqrt N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;

        vector<int> primes;
        for (int i = 2; i*i <= n; ++i) {
            while (n%i == 0) {
                primes.push_back(i);
                n /= i;
            }
        }
        if (n > 1) primes.push_back(n);

        if (size(primes) <= 1) cout << 1 << '\n';
        else if (size(primes) == 2) cout << 2 << '\n';
        else cout << 3 << '\n';
    }
}
1 Like