PRMHOLE - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Jatin Khandual
Testers: Prasanna Kumar
Editorialist: Jatin Khandual

DIFFICULTY:

EASY

PREREQUISITES:

Observations, Pigeonhole Principle, Sieve

PROBLEM:

Given a number N, find the maximum M (not necessarily a prime) such that for all possible multisets of numbers of length N, no number in the multiset has a prime factor greater than M and it is always possible to choose two numbers x and y (from the multiset) such that the product x.y is a perfect square.

QUICK EXPLANATION:

For a given N, the solution is simply (\left \lfloor{\log_2(N - 1)}\right \rfloor + 1)^ {th}\ prime - 1.

EXPLANATION:

Let the prime factorization of a number x in the multiset be {P_1}^{Q_1}.{P_2}^{Q_2}\ldots{P_R}^{Q_R}, where P_i is some prime and Q_i the corresponding power and P_R is the maximum prime allowed in the prime factorization of any number in the list.

Note that this prime-factorization is not the standard one, it includes all the primes till the R^{th} prime with powers greater than or equal to 0.

Observation 1:

We know that, for a number to be a perfect square, parity of all prime powers Q_i in its prime factorization must be even.

Observation 2:

When two numbers, say x with prime factorization {P_1}^{Q_1}.{P_2}^{Q_2}\ldots{P_R}^{Q_R} and y with prime factorization {P_1}^{S_1}.{P_2}^{S_2}\ldots{P_R}^{S_R} are multiplied, the prime powers in the product z just adds up as: {P_1}^{Q_1 + S_1}.{P_2}^{Q_2 + S_2}\ldots{P_R}^{Q_R + S_R}

Observation 3:

Since we want z to be a perfect square, the sums Q_i + S_i must be even, which means that in each pair Q_i-S_i, Q_i and S_i must be of the same parity (either odd-odd or even-even).

The Key:

For a fixed R, the parity of each prime P_i can either be odd or be even. Since there are two choices for each prime, we have a total of 2^R possible ways so that each prime in the prime factorization of a number can have a valid parity (how?). The problem thus reduces to making sure that we always have at least two numbers in the multiset whose prime powers are in total sync with each other in terms of parity.

If we’d to find the minimum N for a given R, it is obvious now that the answer is simply 2^R+1 since N \ge 2^R + 1 (the minimum happens at equality). Now since we’re given N, the inequality becomes R \le \left \lfloor{\log_2(N - 1)}\right \rfloor (the maximum happens at equality. Thus, we found the maximum prime following the given constraints but we need the maximum number, so the solution is simply (\left \lfloor{\log_2(N - 1)}\right \rfloor + 1)^ {th}\ prime - 1.

We can find the primes by our favorite method since R \le 64 as N \le 10^{18}.

SOLUTIONS:

Setter's Solution 
//author: hitch_hiker42;
#include<bits/stdc++.h>
using namespace std;
 
//solution:
#define int int64_t
constexpr int lim = 1001;
vector<int> prime;
 
void limits(int n, int lo, int hi) {
    assert(n >= lo and n <= hi);
}
 
auto sieve() {
    vector<bool> p(lim, true);
    p[0] = p[1] = false;
    for(int i = 3; i < lim / i; i += 2) if(p[i]) {
        for(int j = i * i, k = i << 1; j < lim; j += k) {
            p[j] = false;
        }
    }
    prime.push_back(2);
    for(int i = 3; i < lim; i += 2) if(p[i]) {
        prime.push_back(i);
    }
}
 
void hike() {
    int n; cin >> n;
    limits(n, 2, 1e18);
    cout << prime[(int)(ceill(log2l(n)) - 1)] - 1 << "\n";
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    sieve();
    int t; cin >> t;
    limits(t, 1, 1000);
    while(t--) hike();
    return 0;
} //farewell, until we meet again..
Tester's Solution 
/*****************************
*  Author :: Prasanna Kumar  *
*****************************/

/***********************************
* Unus pro omnibus, omnes pro uno  *
***********************************/
#include<bits/stdc++.h>
using namespace std;

#define __AcHiLlEs ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define __AnAkLuSmOs freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define i_64 long long
#define SZ 100'000
#define MX 1'000'000'000'000'000'000

bool sieve[SZ + 1];
std::vector<i_64> prime;

void solve() {
    i_64 n, cnt(0);
    cin >> n;
    assert(n > 1 and n <= MX);
    n--;
    while (n) cnt++, n >>= 1ll;
    cnt -= 1;
    cout << prime[cnt] - 1 << "\n";
}

signed main() {
    #ifndef ONLINE_JUDGE 
        __AnAkLuSmOs    
    #endif

    __AcHiLlEs

    for (i_64 i = 4; i <= SZ; i += 2) sieve[i] = 1;
    for (i_64 i = 9; i <= SZ; i += 6) sieve[i] = 1;
    for (i_64 i = 5; i * i <= SZ; i += 6) {
    	if (!sieve[i]) {
    		for (i_64 j = i * i; j <= SZ; j += 2 * i) sieve[j] = 1;
    	}
    	if (!sieve[i + 2]) {
    		for (i_64 j = (i + 2) * (i + 2); j <= SZ; j += 2 * (i + 2)) sieve[j] = 1;
    	}
    }
    for (i_64 i = 2; i <= SZ; i++) if (!sieve[i]) prime.push_back(i);
  
    i_64 t(1);
    cin >> t;
    for (i_64 i = 1; i <= t; /*cout << "Case " << i << ": ",*/ solve(), i++);
    return 0;
}
5 Likes