PROBLEM LINK:
Author: Ayesha Uzma
Tester: Anuj Patel
Editorialist: Ayesha Uzma
DIFFICULTY:
Easy
PREREQUISITES:
Sieve Of Eratosthenes
PROBLEM:
There are N sabotages available in the game Among Us, initially all at level 0.
N imposters are allotted the task to upgrade the level of the sabotages.
The i^{th} imposter (1 \leq i \leq N) increases the level of x^{th} sabotage (1 \leq x \leq N) by one level if gcd(i,x)=i.
You need to find the number of sabotages at LEVEL 5 after all the imposters have completed their tasks.
QUICK EXPLANATION:
All sabotages in the range [1, N] of the form prime^4 are at level 5.
EXPLANATION:
All the N sabotages are initially at level 0.
The level of x^{th} sabotage increases if gcd(i,x)=i. This means that the level increases if i is a factor of x.
For example:
When N = 6, the 6 sabotages reach levels as given below:
1^{st} SABOTAGE : level 1 (by the 1^{st} imposter)
2^{nd} SABOTAGE : level 2 (by 1^{st} & 2^{nd} imposters)
3^{rd} SABOTAGE : level 2 (by 1^{st} & 3^{rd} imposters)
4^{th} SABOTAGE : level 3 (by 1^{st}, 2^{nd} & 4^{th} imposters)
5^{th} SABOTAGE : level 2 (by 1^{st} & 5^{th} imposters)
6^{th} SABOTAGE : level 4 (by 1^{st}, 2^{nd}, 3^{rd} & 6^{th} imposters)
None of them reach level 5.
Hence you need to find the sabotages having exactly 5 factors. Numbers of the form prime^4 have exactly 5 factors .
Let the prime factorization of N be (p_1^{a_1})*(p_2^{a_2})...(p_n^{a_n}), where p_i (1 \leq i \leq n) are distinct primes, then the total number of factors are (a_1+1)*(a_2+1)...(a_n+1).
But we need prime number of factors, 5. This cannot be yielded with (a_1+1)*(a_2+1)...(a_n+1) when a_2,a_3,...a_n \geq 1, hence there is only one prime factor.
Hence p_1^{a_1} should result in 5 factors.
(a_1+1)=5
Therefore a_1=4
Hence numbers of the form prime^4 have exactly 5 factors.
We can use sieve of Eratosthenes to find all the prime numbers in the range [1, \sqrt{\sqrt{N}} ] and precompute the count of prime numbers using prefix sum.
When N=10^{18}, \sqrt{\sqrt{N}} \le 10^5 therefore we can calculate sieve for the first 10^5 numbers.
Time Complexity:
The time complexity is O(Nlog(logN)) for precomputation and O(1) per test case which makes the overall time complexity O(T+Nlog(logN)).
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
int main()
{
//fast_io
int prime[100001]={0},pre[100001]={0};
for(ll p=2;p<=100000;p++)
prime[p]=1;
for (ll p=2; p*p<=100000; p++)
{
if (prime[p] == 1)
{
for (ll i=p*p; i<=100000; i += p)
prime[i] = 0;
}
}
for(ll i=2;i<=100000;i++)
pre[i]=prime[i]+pre[i-1];
ll t;
cin>>t;
assert(1 <= t && t <= 100000);
while(t--)
{
ll n;
cin>>n;
assert(1 <= n && n <= 1e18);
ll s=sqrtl(sqrtl(n));
cout<<pre[s]<<endl;
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
#define flash ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
vector<ll> pr;
void sieve(int n=34688)
{
bool prime[n+1];
memset(prime, true, sizeof(prime));
for (int p=2; p*p<=n; p++)
{
if (prime[p] == true)
{
for (int i=p*p; i<=n; i += p)
prime[i] = false;
}
}
for (ll p=2; p<=n; p++) {
ll val = p*p*p*p;
if (prime[p]) pr.push_back(val);
}
}
int main() {
flash;
sieve();
int T;cin>>T;
assert(1<= T && T<= 1e5);
ll n;
while(T--)
{
cin>>n;
assert(1<=n && n<=1e18);
auto ind = lower_bound(pr.begin(),pr.end(),n) - pr.begin();
if(pr[ind]==n)
ind++;
cout<<ind<<endl;
}
return 0;
}