范围在(a[i], a[j])中，可被x整除的k个数字的偶对数量（a[j] >= a[i]）
原文： 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)。
有效方法是对数组进行排序，然后使用二分搜索找出数字的左右边界（使用lower_bound函数内置函数可以做到） 满足条件而哪些不满足。 我们必须对数组进行排序，因为给出的每对数组均应为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 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 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
# 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)。
版权属于：月萌API www.moonapi.com，转载请注明出处
