给定N个数字和Q个查询，每个查询都由L和R组成。任务是编写一个程序，打印数字计数，将给定范围L-R内的所有数字除以。 例如：
null
Input : a = {3, 4, 2, 2, 4, 6} Q = 2 L = 1 R = 4 L = 2 R = 6 Output : 0 2 Explanation : The range 1-4 has {3, 4, 2, 2} which does not have any number that divides all the numbers in this range. The range 2-6 has {4, 2, 2, 4, 6} which has 2 numbers {2, 2} which divides all numbers in the given range. Input: a = {1, 2, 3, 5} Q = 2 L = 1 R = 4 L = 2 R = 4 Output: 1 0
天真的方法： 对每个查询从范围L-R进行迭代，并检查索引i处的给定元素是否除以范围内的所有数字。我们计算所有除以这些数的元素的个数。在最坏的情况下，每个查询的复杂性都将是 O（n） 2. ) . 下面是Naive方法的实现：
C++
// CPP program to Count elements which // divides all numbers in range L-R #include <bits/stdc++.h> using namespace std; // function to count element // Time complexity O(n^2) worst case int answerQuery( int a[], int n, int l, int r) { // answer for query int count = 0; // 0 based index l = l - 1; // iterate for all elements for ( int i = l; i < r; i++) { int element = a[i]; int divisors = 0; // check if the element divides // all numbers in range for ( int j = l; j < r; j++) { // no of elements if (a[j] % a[i] == 0) divisors++; else break ; } // if all elements are divisible by a[i] if (divisors == (r - l)) count++; } // answer for every query return count; } // Driver Code int main() { int a[] = { 1, 2, 3, 5 }; int n = sizeof (a) / sizeof (a[0]); int l = 1, r = 4; cout << answerQuery(a, n, l, r) << endl; l = 2, r = 4; cout << answerQuery(a, n, l, r) << endl; return 0; } |
JAVA
// Java program to Count elements which // divides all numbers in range L-R import java.io.*; class GFG { // function to count element // Time complexity O(n^2) worst case static int answerQuery( int a[], int n, int l, int r) { // answer for query int count = 0 ; // 0 based index l = l - 1 ; // iterate for all elements for ( int i = l; i < r; i++) { int element = a[i]; int divisors = 0 ; // check if the element divides // all numbers in range for ( int j = l; j < r; j++) { // no of elements if (a[j] % a[i] == 0 ) divisors++; else break ; } // if all elements are divisible by a[i] if (divisors == (r - l)) count++; } // answer for every query return count; } // Driver Code public static void main (String[] args) { int a[] = { 1 , 2 , 3 , 5 }; int n = a.length; int l = 1 , r = 4 ; System.out.println( answerQuery(a, n, l, r)); l = 2 ; r = 4 ; System.out.println( answerQuery(a, n, l, r)); } } // This code is contributed by anuj_67.. |
Python3
# Python 3 program to Count elements which # divides all numbers in range L-R # function to count element # Time complexity O(n^2) worst case def answerQuery(a, n, l, r): # answer for query count = 0 # 0 based index l = l - 1 # iterate for all elements for i in range (l, r, 1 ): element = a[i] divisors = 0 # check if the element divides # all numbers in range for j in range (l, r, 1 ): # no of elements if (a[j] % a[i] = = 0 ): divisors + = 1 else : break # if all elements are divisible # by a[i] if (divisors = = (r - l)): count + = 1 # answer for every query return count # Driver Code if __name__ = = '__main__' : a = [ 1 , 2 , 3 , 5 ] n = len (a) l = 1 r = 4 print (answerQuery(a, n, l, r)) l = 2 r = 4 print (answerQuery(a, n, l, r)) # This code is contributed by # Shashank_Sharma |
C#
// C# program to Count elements which // divides all numbers in range L-R using System; class GFG { // function to count element // Time complexity O(n^2) worst case static int answerQuery( int []a, int n, int l, int r) { // answer for query int count = 0 ; // 0 based index l = l - 1 ; // iterate for all elements for ( int i = l; i < r; i++) { //int element = a[i]; int divisors = 0 ; // check if the element divides // all numbers in range for ( int j = l; j < r; j++) { // no of elements if (a[j] % a[i] == 0 ) divisors++; else break ; } // if all elements are divisible by a[i] if (divisors == (r - l)) count++; } // answer for every query return count; } // Driver Code public static void Main () { int []a = { 1 , 2 , 3 , 5 }; int n = a.Length; int l = 1 , r = 4 ; Console.WriteLine(answerQuery(a, n, l, r)); l = 2 ; r = 4 ; Console.WriteLine(answerQuery(a, n, l, r)); } } // This code is contributed by anuj_67.. |
PHP
<?php // PHP program to Count elements which // divides all numbers in range L-R // function to count element // Time complexity O(n^2) worst case function answerQuery( $a , $n , $l , $r ) { // answer for query $count = 0; // 0 based index $l = $l - 1; // iterate for all elements for ( $i = $l ; $i < $r ; $i ++) { $element = $a [ $i ]; $divisors = 0; // check if the element divides // all numbers in range for ( $j = $l ; $j < $r ; $j ++) { // no of elements if ( $a [ $j ] % $a [ $i ] == 0) $divisors ++; else break ; } // if all elements are divisible by a[i] if ( $divisors == ( $r - $l )) $count ++; } // answer for every query return $count ; } // Driver Code $a = array (1, 2, 3, 5); $n = sizeof( $a ); $l = 1; $r = 4; echo answerQuery( $a , $n , $l , $r ) . "" ; $l = 2; $r = 4; echo answerQuery( $a , $n , $l , $r ) . "" ; // This code is contributed // by Akanksha Rai |
Javascript
<script> // javascript program to Count elements which // divides all numbers in range L-R // function to count element // Time complexity O(n^2) worst case function answerQuery(a , n , l , r) { // answer for query var count = 0; // 0 based index l = l - 1; // iterate for all elements for (i = l; i < r; i++) { var element = a[i]; var divisors = 0; // check if the element divides // all numbers in range for (j = l; j < r; j++) { // no of elements if (a[j] % a[i] == 0) divisors++; else break ; } // if all elements are divisible by a[i] if (divisors == (r - l)) count++; } // answer for every query return count; } // Driver Code var a = [ 1, 2, 3, 5 ]; var n = a.length; var l = 1, r = 4; document.write(answerQuery(a, n, l, r)+ "<br/>" ); l = 2; r = 4; document.write(answerQuery(a, n, l, r)); // This code is contributed by gauravrajput1 </script> |
输出：
10
有效方法： 使用 分段树 来解决这个问题。如果一个元素将给定范围内的所有数字相除，那么该元素是该范围内的最小数，它是给定范围L-R内所有元素的gcd。因此，如果最小值等于该范围内的gcd，那么L-R范围内的最小数目的计数将是我们对每个查询的答案。问题归根结底在于找到正确的答案 GCD , 最低限度 和 计数最小值 对于每个范围，使用分段树。在树的每个节点上，存储三个值。 在查询给定范围时，如果给定范围的gcd和最小值相等， 计数最小值 作为答案返回。如果它们不相等，则返回0作为答案。 以下是高效方法的实施：
CPP
// CPP program to Count elements // which divides all numbers in // range L-R efficient approach #include <bits/stdc++.h> using namespace std; #define N 100005 // predefines the tree with nodes // storing gcd, min and count struct node { int gcd; int min; int cnt; } tree[5 * N]; // function to construct the tree void buildtree( int low, int high, int pos, int a[]) { // base condition if (low == high) { // initially always gcd and min // are same at leaf node tree[pos].min = tree[pos].gcd = a[low]; tree[pos].cnt = 1; return ; } int mid = (low + high) >> 1; // left-subtree buildtree(low, mid, 2 * pos + 1, a); // right-subtree buildtree(mid + 1, high, 2 * pos + 2, a); // finds gcd of left and right subtree tree[pos].gcd = __gcd(tree[2 * pos + 1].gcd, tree[2 * pos + 2].gcd); // left subtree has the minimum element if (tree[2 * pos + 1].min < tree[2 * pos + 2].min) { tree[pos].min = tree[2 * pos + 1].min; tree[pos].cnt = tree[2 * pos + 1].cnt; } // right subtree has the minimum element else if (tree[2 * pos + 1].min > tree[2 * pos + 2].min) { tree[pos].min = tree[2 * pos + 2].min; tree[pos].cnt = tree[2 * pos + 2].cnt; } // both subtree has the same minimum element else { tree[pos].min = tree[2 * pos + 1].min; tree[pos].cnt = tree[2 * pos + 1].cnt + tree[2 * pos + 2].cnt; } } // function that answers every query node query( int s, int e, int low, int high, int pos) { node dummy; // out of range if (e < low or s > high) { dummy.gcd = dummy.min = dummy.cnt = 0; return dummy; } // in range if (s >= low and e <= high) { node dummy; dummy.gcd = tree[pos].gcd; dummy.min = tree[pos].min; if (dummy.gcd != dummy.min) dummy.cnt = 0; else dummy.cnt = tree[pos].cnt; return dummy; } int mid = (s + e) >> 1; // left-subtree node ans1 = query(s, mid, low, high, 2 * pos + 1); // right-subtree node ans2 = query(mid + 1, e, low, high, 2 * pos + 2); node ans; // when both left subtree and // right subtree is in range if (ans1.gcd and ans2.gcd) { // merge two trees ans.gcd = __gcd(ans1.gcd, ans2.gcd); ans.min = min(ans1.min, ans2.min); // when gcd is not equal to min if (ans.gcd != ans.min) ans.cnt = 0; else { // add count when min is // same of both subtree if (ans1.min == ans2.min) ans.cnt = ans2.cnt + ans1.cnt; // store the minimal's count else if (ans1.min < ans2.min) ans.cnt = ans1.cnt; else ans.cnt = ans2.cnt; } return ans; } // only left subtree is in range else if (ans1.gcd) return ans1; // only right subtree is in range else if (ans2.gcd) return ans2; } // function to answer query in range l-r int answerQuery( int a[], int n, int l, int r) { // calls the function which returns // a node this function returns the // count which will be the answer return query(0, n - 1, l - 1, r - 1, 0).cnt; } // Driver Code int main() { int a[] = { 3, 4, 2, 2, 4, 6 }; int n = sizeof (a) / sizeof (a[0]); buildtree(0, n - 1, 0, a); int l = 1, r = 4; // answers 1-st query cout << answerQuery(a, n, l, r) << endl; l = 2, r = 6; // answers 2nd query cout << answerQuery(a, n, l, r) << endl; return 0; } |
输出：
02
时间复杂性： 树构造的时间复杂度是 O（n logn） 因为树的构造需要O（n），而找出gcd需要O（logn）。在最坏的情况下，每个查询所需的时间将是 O（logn*logn），因为内置函数u gcd取O（logn）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
