PROBLEM LINK:
DIFFICULTY:
Easy
PREREQUISITES:
Sieve of Eratosthenes
PROBLEM:
You are given a positive integers N . We can prove that every N can be divided by x_i, where x and i both are positive integers and x>1. For each N, find out the value of x for which i will be maximum. If multiple solutions exist, then print the maximum value of x.
QUICK EXPLANATION:
Precompute all the primes less than the maximum value of N and store them in the array. For each of the primes i, i \leq \sqrt{N}, calculate the number of times they occur in N. Multiply all the primes occurring the maximum number of times.
EXPLANATION:
Observation 1:
We can’t check for every divisor until \sqrt{N} because of the constraints, as there can be at most 5 \cdot 10^5 \cdot \sqrt(10^6) \cdot {log_2(10^6)}.
Observation 2:
Every composite number can occur at most min(P_i), among all P_i prime divisors of it. Thus, we can just calculate the number of occurrences of every prime and multiply the most occuring ones together at the end.
How do we combine all of this?
It’s very simple. Firstly, we’ll need to use Sieve of Eratosthenes to precompute every prime less than \sqrt{N} in O(N log N) time and store them in a temporary array. There are only 168 primes \leq \sqrt{N}.
We can see that if prime P_i occurs x times and P_j occurs x times, then P_i \cdot P_j occurs x times as well. We can also see that all the primes between P_i and P_j occur at most x times, if the two exist. If it weren’t the case, than P_k would occur more times and thus discard both the values in the answers as we are looking for the maximum occuring one.
So this gives us all the necessary steps. For every prime that is a potential divisor of N calculate the number of times it occurs by simple division and consider multiple cases:
- C_i occurs more times than current C_{max} \implies set C_{max} = C_i and change the counter of maximum occurring divisor
- C_i occurs less times than current C_{max} \implies do nothing, go to next divisor
- C_i occurs the same number of times as the current C_{max} \implies multiply current C_{max} by C_i, meaning set C_{max} = C_i \cdot C_{max}, keep the counter as is
SOLUTIONS:
Alternate Editorialist's Solution:
#include <bits/stdc++.h>
using namespace std;
int t, n;
const int MAXN = 1e6;
bool prime[MAXN + 10];
vector<int> primes;
void sieve() {
for (int i = 2; i <= MAXN; i++) {
if (!prime[i]) continue;
primes.push_back(i);
for (long long j = 1LL * i * i; j <= MAXN; j += i) {
prime[j] = 0;
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
memset(prime, 1, sizeof prime);
sieve();
cin >> t;
while (t--) {
cin >> n;
int mx = -1, cc = -1;
for (int i = 0; i < primes.size() && primes[i] * primes[i] <= n; i++) {
int tmp = n;
int cnt = 0;
while (tmp % primes[i] == 0) {
tmp /= primes[i];
cnt++;
}
if (cnt) {
if (mx == -1) {
mx = primes[i];
cc = cnt;
} else if (cnt > cc) {
mx = primes[i];
cc = cnt;
} else if (cnt == cc) {
mx *= primes[i];
}
}
}
if (mx == -1 || cc <= 1) {
mx = n;
}
cout << mx << '\n';
}
return 0;
}