對數（a [j] > = a [i]）的對數，其中 k 個范圍在（a [i]，a [j]）中，可被 x 整除 · GeeksForGeeks 中文系列教程

# 對數（a [j] > = a [i]）的對數，其中 k 個范圍在（a [i]，a [j]）中，可被 x 整除 > 原文： [https://www.geeksforgeeks.org/no-pairs-aj-ai-k-numbers-range-ai-aj-divisible-x/](https://www.geeksforgeeks.org/no-pairs-aj-ai-k-numbers-range-ai-aj-divisible-x/) 給定一個數組和兩個數字 x 和 k。找出索引（i，j）的不同有序對的數量，使得 a [j] > = a [i]，并且正好有 k 個整數 num，使得 num 可被 x 整除，并且 num 在 a [i]范圍內 ] -a [j]。 **示例**： ``` Input : arr[] = {1, 3, 5, 7} x = 2, k = 1 Output : 3 Explanation: The pairs (1, 3), (3, 5) and (5, 7) have k (which is 1) integers i.e., 2, 4, 6 respectively for every pair in between them. Input : arr[] = {5, 3, 1, 7} x = 2, k = 0 Output : 4 Explanation: The pairs with indexes (1, 1), (2, 2), (3, 3), (4, 4) have k = 0 integers that are divisible by 2 in between them. ``` **樸素方法**會遍歷所有可能的對，并計算在它們之間具有 k 個整數的對數，這些整數可被 x 整除。 **時間復雜度**： O（n ^ 2） **有效方法**是對數組進行排序，然后使用[二分搜索](https://www.geeksforgeeks.org/binary-search/)找出數字的左右邊界（使用 [lower_bound 函數](https://www.geeksforgeeks.org/upper_bound-and-lower_bound-for-vector-in-cpp-stl/)內置函數可以做到）滿足條件而哪些不滿足。我們必須對數組進行排序，因為給出的每對數組均應為 a [j] > = a [i]，而與 i 和 j 的值無關。排序后，我們遍歷 n 個元素，并找到與 x 相乘得到 a [i] -1 的數字，以便我們可以通過將 d 加到 d = a [i] -1 / x 來找到 k 個數。因此，我們對值（d + k）* x 進行二分搜索，以獲取可以構成一對 a [i]的倍數，因為它將在 a [i]和 a [j]之間恰好有 k 個整數。這樣，我們在`O(log n)`中使用二分搜索獲得 a [j]的左邊界，對于所有其他可能使用 a [i]的對，我們需要通過搜索等于的數來找出最右邊界等于或大于（d + k + 1）* x，在這里我們將得到 k + 1 倍，并且我們得到的結對數（作為（左右方向）邊界）。 ## C++ ```cpp // cpp program to calculate the number // pairs satisfying th condition #include <bits/stdc++.h> using namespace std; // function to calculate the number of pairs int countPairs(int a[], int n, int x, int k) { ????sort(a, a + n);???? ????// traverse through all elements ????int ans = 0; ????for (int i = 0; i < n; i++) { ????????// current number's divisor ????????int d = (a[i] - 1) / x; ????????// use binary search to find the element? ????????// after k multiples of x ????????int it1 = lower_bound(a, a + n,? ?????????????????????????max((d + k) * x, a[i])) - a; ????????// use binary search to find the element ????????// after k+1 multiples of x so that we get? ????????// the answer bu subtracting ????????int it2 = lower_bound(a, a + n, ?????????????????????max((d + k + 1) * x, a[i])) - a; ????????// the difference of index will be the answer ????????ans += it2 - it1; ????} ????return ans; } // driver code to check the above fucntion int main() { ????int a[] = { 1, 3, 5, 7 }; ????int n = sizeof(a) / sizeof(a[0]); ????int x = 2, k = 1; ????// function call to get the number of pairs ????cout << countPairs(a, n, x, k); ????return 0; } ``` ## Java ```java // Java program to calculate the number // pairs satisfying th condition import java.util.*;? class GFG { // function to calculate the number of pairs static int countPairs(int a[], int n, int x, int k) { ????Arrays.sort(a);? ????// traverse through all elements ????int ans = 0; ????for (int i = 0; i < n; i++)? ????{ ????????// current number's divisor ????????int d = (a[i] - 1) / x; ????????// use binary search to find the element? ????????// after k multiples of x ????????int it1 = Arrays.binarySearch(a,? ????????????????????Math.max((d + k) * x, a[i])); ????????// use binary search to find the element ????????// after k+1 multiples of x so that we get? ????????// the answer bu subtracting ????????int it2 = Arrays.binarySearch(a, ????????????????????Math.max((d + k + 1) * x, a[i])) ; ????????// the difference of index will be the answer ????????ans += it1 - it2; ????} ????return ans; } // Driver code? public static void main(String[] args) { ????int []a = { 1, 3, 5, 7 }; ????int n = a.length; ????int x = 2, k = 1; ????// function call to get the number of pairs ????System.out.println(countPairs(a, n, x, k)); } } // This code is contributed by Rajput-Ji ``` ## Python3 ```py # Python program to calculate the number # pairs satisfying th condition import bisect # function to calculate the number of pairs def countPairs(a, n, x, k): ????a.sort() ????# traverse through all elements ????ans = 0 ????for i in range(n): ????????# current number's divisor ????????d = (a[i] - 1) // x ????????# use binary search to find the element ????????# after k multiples of x ????????it1 = bisect.bisect_left(a, max((d + k) * x, a[i])) ????????# use binary search to find the element ????????# after k+1 multiples of x so that we get ????????# the answer bu subtracting ????????it2 = bisect.bisect_left(a, max((d + k + 1) * x, a[i])) ????????# the difference of index will be the answer ????????ans += it2 - it1 ????return ans # Driver code if __name__ == "__main__": ????a = [1, 3, 5, 7] ????n = len(a) ????x = 2 ????k = 1 ????# function call to get the number of pairs ????print(countPairs(a, n, x, k)) # This code is contributed by # sanjeev2552 ``` **輸出**： ``` 3 ``` **時間復雜度**：`O(N log N)` * * * * * *