REC15B - Editorial



Author: Ayesha Uzma
Tester: Anuj Patel
Editorialist: Ayesha Uzma




Sieve Of Eratosthenes


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.


All sabotages in the range [1, N] of the form prime^4 are at level 5.


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.
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)).


Setter's Solution
#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()
     int prime[100001]={0},pre[100001]={0};

    for(ll p=2;p<=100000;p++)

    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++)

    ll t;
    assert(1 <= t && t <= 100000);

        ll n;
        assert(1 <= n && n <= 1e18);

        ll s=sqrtl(sqrtl(n));

    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() {
    int T;cin>>T;
    assert(1<= T && T<= 1e5);
    ll n;
        assert(1<=n && n<=1e18);
        auto ind = lower_bound(pr.begin(),pr.end(),n) - pr.begin();
    return 0;

I like this contest.
I can learn more and more in this kind of short time contests.

1 Like