AREA21

Two Aliens Garrix and Maejor decided that its time to save mother Earth from all the destruction that is being caused. They saw so much hate and saw many things they did not want to see. They saw people fighting, missiles flying, babies crying and even people lying. So they decided its high time they get to work.  But they need to start off at someplace, so they decided that place to be AREA21. But to land there they need proper coordinates which can be only deduced by processing a given array and finding its answer. Please help these guys so that they can get to work ..

Given an array of integers, some queries will be asked on the following array. In each query, there will be two values L and R . They need to find how many indices  L<=i<=R in the given range are good indices.
Property: A Good index is the one that satisfies a property of EulerTotient(A[i])=(A[i]1).
Note: L and R are considered in one-based indexing.

Euler's totient function counts the positive integers up to a given integer N that are relatively prime to it. 

Example:

Input: n = 4, q = 1, a = [2,3,5,7],  l =1, r= 4
Output: 4

Approach

C++

#include <bits/stdc++.h>
using namespace std;

int arr[100001];
int tree[200010];
void build(int nodeint startint end)
{
    if (start == end)
    {
        tree[node] = arr[start];
    }
    else
    {
        int mid = (start + end) / 2;
        build(2 * nodestartmid);
        build(2 * node + 1mid + 1end);
        tree[node] = tree[2 * node] + tree[2 * node + 1];
    }
}
int query(int nodeint startint endint lint r)
{
    if (r < start || l > end)
        return 0;
    if (l <= start && r >= end)
        return tree[node];
    int mid = (start + end) / 2;
    int p1 = query(node * 2startmidlr);
    int p2 = query(node * 2 + 1mid + 1endlr);
    return p1 + p2;
}
int main()
{
    bool prime[1000001];
    memset(primetruesizeof(prime));
    prime[0] = false;
    prime[1] = false;
    for (int i = 2i * i <= 1000001i++)
    {
        if (prime[i])
        {
            for (int j = i * ij <= 1000001j += i)
                prime[j] = false;
        }
    }
    int n = 4q = 1;

    int a[n] = {2357};

    for (int i = 0i < ni++)
    {
        if (prime[a[i]])
            arr[i + 1] = 1;
        else
            arr[i + 1] = 0;
    }

    build(11n);

    int l = 1r = 4;

    int ans = query(11nlr);
    cout << ans << "\n";
    return 0;
}


No comments:

Post a Comment