Количество пар, у которых модуль произведения единицы с их XOR и X равен 1
Имея два массива A[] и B[] длины N и M соответственно и простое число X , задача состоит в том, чтобы найти количество упорядоченных пар индексов (i, j), удовлетворяющих следующим условиям:
- 1 ≤ i ≤ N и 1 ≤ j ≤ M
- ( А я ⊕ В j ) < Икс
- (( А я ⋅ ( А я ⊕ Bj )) - 1) % X = 0
Примечание: ⊕ — это оператор XOR.
Примеры:
Input: A[] = {7, 14} , B = {2, 13}, X = 17
Output: 1
Explanation: There are 4 ordered pairs of indices. Looking at them individually,
(1, 1) satisfies because (7 ⊕ 2) = 5 < 17, and ((7⋅ (7 ⊕ 2)) − 1) = 34 is divisible by 17.
(1, 2) satisfies because (7 (7 ⊕ 13)) − 1) = 69 is not divisible by 17.
(2, 1) satisfies because ((14⋅(14 ⊕ 2)) − 1) = 167 is not divisible by 17
(2, 2) satisfies because ((14⋅(14 ⊕ 13)) − 1) = 41 is not divisible by 17.Input: A[] = {3} , B = {3}, X = 11
Output: 0
Подход: Задача может быть решена на основе следующего математического наблюдения:
Consider two values Ai and Bj which satisfies the condition.
So, ( Ai⋅( Ai ⊕ Bj )−1) mod X = 0
(( Ai⋅( Ai ⊕ Bj )) mod X = 1
( Ai ⊕ Bj ) mod X = Ai−1 mod X
( Ai ⊕ Bj )= Ai−1 mod X (according to the last condition)
Bj = ( Ai ⊕ ( Ai-1 mod X ))So if the value of Ai is known we can easily check if there is any value in B[] that satisfies the condition.
Для реализации идеи выполните следующие шаги:
- Сохраните все элементы B[] на карте.
- Проходим через массив A[] :
- Обратите внимание, что если значения A[i] и X не являются простыми, то условие не может быть выполнено, поскольку мы не можем получить некоторое число, кратное A[i] , которое даст 1 в качестве остатка при делении на X .
- В противном случае вычислите значение из B, которое будет удовлетворять условию, используя приведенную выше формулу.
- Найдите количество этого значения и добавьте его к ответу.
- Возвращает окончательное значение ответа.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O (N * log X)
Вспомогательное пространство: O(1)