HackerRank Number Theory – Divisibility of Power

Challenge: Divisibility of Power

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464742999

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/divisibility-of-power/problem

Cerinta

You are given an array $A$ of size $N$. You are asked to answer $Q$ queries. 

Each query is of the form : 

$\text{i j x}$ 

You need to print `Yes` if $x$ divides the value returned from $find(i,j)$ function, otherwise print `No`.

	find(int i,int j)
	{
        if(i>j)	return 1;
        ans = pow(A[i],find(i+1,j))
        return ans
    }

**Input Format**

First line of the input contains $N$. Next line contains $N$ space separated numbers. The line, thereafter, contains $Q$ , the number of queries to follow. Each of the next $Q$ lines contains three positive integer $i$, $j$ and $x$.

**Output Format**

For each query display `Yes` or `No` as explained above.

**Constraints**  
$2 \le N \le 2 \times 10^{5}$  
$2 \le Q \le 3 \times 10^{5}$  
$1 \le i,j \le N$  
$i \le j$  
$1 \le x \le 10^{16}$  
$0 \le $ value of array element $\le 10^{16}$

No 2 consecutive entries in the array will be zero.

**Sample Input**

    4
    2 3 4 5
    2
    1 2 4
    1 3 7

**Sample Output**

    Yes
    No

Cod sursa

//divisibility-of-power.cpp
//Divisibility of Power
//Ad Infinitum - Math Programming Contest August'14
//Author: derekhh

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

long long mulmod(long long a, long long b, long long m) 
{
	long long res = 0;
	while (a != 0) 
	{
		if (a & 1) res = (res + b) % m;
		a >>= 1;
		b = (b << 1) % m;
	}
	return res;
}

long long ModExp(long long a, long long b, long long n)
{
	long long c = 1, d = a;
	while (b)
	{
		if (b & 1) c = mulmod(c, d, n);
		d = mulmod(d, d, n);
		b >>= 1;
	}
	return c % n;
}

long long a[300001];

int foo(long long a, long long b)
{
	if (a < 2) return (int)a;
	if (b == 0) return 1;
	if (b == 1) 
	{
		if (a > 64) return 64;
		return (int) a;
	}
	if (a > 8 || b > 6) return 64;
	int ret = (int)pow(a, b);
	return ret > 64 ? 64 : ret;
}

int main()
{
	long long n;
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]);
	long long q;
	scanf("%lld", &q);
	while (q--)
	{
		long long i, j, x;
		scanf("%lld%lld%lld", &i, &j, &x);
		int res = 1;
		int k = min(j, i + 6);
		if (i + 7 <= j && a[i + 7] == 0) k--;
		for (; k > i; k--)
			res = foo(a[k], res);
		long long ans = ModExp(a[i], res, x);
		if (ans == 0) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}