Количество пар, у которых модуль произведения единицы с их XOR и X равен 1

Опубликовано: 25 Февраля, 2023

Имея два массива 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:

Подход: Задача может быть решена на основе следующего математического наблюдения:

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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ