首页 > 代码库 > Hackerrank--Divisibility of Power(Math)

Hackerrank--Divisibility of Power(Math)

2024-07-18 00:42:17   220人阅读

题目链接

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

Each query is of the form :

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≤N≤2×105 
2≤Q≤3×105 
1≤i,j≤N 
i≤j 
1≤x≤1016 
0≤ value of array element ≤1016

No 2 consecutive entries in the array will be zero.

Sample Input

42 3 4 521 2 41 3 7

Sample Output

YesNo

首先，对于每次询问（i，j，x）， 如果x中含有a[i]中没有的质因子，那么一定是No
其次，求出需要几个a[i]才能被x整除之后（设为cnt），就需要判断find(i+1, j)和cnt的大小。
对于a[i] = 0 或者 1 的情况可以进行特判，其他情况，因为x不大于1e16,所以可以直接暴力。
Accepted Code:
  1 #include <cstdio>  2 #include <cstring>  3 #include <cstdlib>  4 #include <iostream>  5 using namespace std;  6 const int maxn = 200002;  7 typedef long long LL;  8 const int inf = 0x3f3f3f3f;  9 LL a[maxn], x; 10 int n, Q, i, j, cnt, near0[maxn], near1[maxn], c[maxn]; 11 bool flag; 12  13 void init() { 14     memset(near0, 0x3f, sizeof(near0)); 15     memset(near1, 0x3f, sizeof(near1)); 16     cnt = 0; 17     for (i = 1; i <= n; i++) if (a[i] == 0) c[cnt++] = i; 18     int be = 1; 19     for (i = 0; i < cnt; i++) { 20         for (j = be; j < c[i]; j++) near0[j] = c[i]; 21         be = c[i] + 1; 22     } 23     cnt = 0; 24     for (i = 1; i <= n; i++) if (a[i] == 1) c[cnt++] = i; 25     be = 1; 26     for (i = 0; i < cnt; i++) { 27         for (j = be; j < c[i]; j++) near1[j] = c[i]; 28         be = c[i] + 1; 29     } 30 } 31  32 void read(LL &res) { 33     res = 0; 34     char c = ‘ ‘; 35     while (c < ‘0‘ || c > ‘9‘) c = getchar(); 36     while (c >= ‘0‘ && c <= ‘9‘) res = res * 10 + c - ‘0‘, c = getchar(); 37 } 38 void read(int &res) { 39     res = 0; 40     char c = ‘ ‘; 41     while (c < ‘0‘ || c > ‘9‘) c = getchar(); 42     while (c >= ‘0‘ && c <= ‘9‘) res = res * 10 + c - ‘0‘, c = getchar(); 43 } 44  45 LL gcd(LL a, LL b) { 46     if (!b) return a; 47     else return gcd(b, a % b); 48 } 49  50 bool ok(int be, int en) { 51     LL res = 1; 52     for (int i = en; i >= be; i--) { 53         //if (quick_pow(a[i], res, res)) return true; 54         LL tmp = 1; 55         for (int j = 0; j < res; j++) { 56             if (tmp >= cnt || a[i] >= cnt) return true; 57             tmp *= a[i]; 58         } 59         if (tmp >= cnt) return true; 60         res = tmp; 61     } 62     return res >= cnt; 63 } 64 int main(void) { 65     read(n); 66     for (i = 1; i <= n; i++) read(a[i]); 67     init(); 68     read(Q); 69     while (Q--) { 70         read(i), read(j), read(x); 71         if (a[i] == 0) { 72             puts("Yes"); continue; 73         } 74         if (x == 1) { 75             puts("Yes"); continue; 76         } 77         if (a[i] == 1) { 78             puts("No"); continue; 79         } 80         if (a[i+1] == 0 && j >= i + 1) { 81             puts("No"); continue; 82         } 83         cnt = 0; flag = true; 84         while (x != 1) { 85             LL tmp = gcd(x, a[i]); 86             if (tmp == 1) { 87                 flag = false; break; 88             } 89             while (x % tmp == 0) x /= tmp, ++cnt; 90         } 91         if (near0[i] <= j) j = min(j, near0[i] - 2); 92         if (near1[i] <= j) j = min(j, near1[i] - 1); 93         if (j == i) { 94             if (!flag || cnt > 1) puts("No"); 95             else if (a[i] % x == 0) puts("Yes"); 96             else puts("No"); 97             continue; 98         } 99         if (!flag || !ok(i+1, j)) puts("No");100         else puts("Yes");101     }102     return 0;103 }

 

































        

            
                
                  
                
                

                    联系

                    我们