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 and . They need to find how many indices in the given range are good indices.
Property: A Good index is the one that satisfies a property of .
Note: and are considered in one-based indexing.
Euler's totient function counts the positive integers up to a given integer 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 node, int start, int end){if (start == end){tree[node] = arr[start];}else{int mid = (start + end) / 2;build(2 * node, start, mid);build(2 * node + 1, mid + 1, end);tree[node] = tree[2 * node] + tree[2 * node + 1];}}int query(int node, int start, int end, int l, int 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 * 2, start, mid, l, r);int p2 = query(node * 2 + 1, mid + 1, end, l, r);return p1 + p2;}int main(){bool prime[1000001];memset(prime, true, sizeof(prime));prime[0] = false;prime[1] = false;for (int i = 2; i * i <= 1000001; i++){if (prime[i]){for (int j = i * i; j <= 1000001; j += i)prime[j] = false;}}int n = 4, q = 1;int a[n] = {2, 3, 5, 7};for (int i = 0; i < n; i++){if (prime[a[i]])arr[i + 1] = 1;elsearr[i + 1] = 0;}build(1, 1, n);int l = 1, r = 4;int ans = query(1, 1, n, l, r);cout << ans << "\n";return 0;}
No comments:
Post a Comment