algorithm - 查找对数，其索引的乘积可被另一个数 X 整除

Question

i < j给定一个数组和某个值 X ，找出满足a[i] = a[j]和(i * j) % X == 0

Array size <= 10^5

我正在考虑这个问题一段时间，但只能提出暴力解决方案（通过检查所有对），这显然会超时[O(N^2) time complexity]

有更好的方法吗？

标签： algorithmsortingmathdata-structures

Answer 1

First of all, store separate search structures for each distinct A[i] as we iterate.

i * j = k * X
i = k * X / j

Let X / j be some fraction. Since i is an integer, k would be of the form m * least_common_multiple(X, j) / X, where m is natural.

Example 1: j = 20, X = 60:

lcm(60, 20) = 60
matching `i`s would be of the form:
(m * 60 / 60) * 60 / 20
=> m * q, where q = 3

Example 2: j = 6, X = 2:

lcm(2, 6) = 6
matching `i`s would be of the form:
(m * 6 / 2) * 2 / 6
=> m * q, where q = 1

Next, I would consider how to efficiently query the number of multiples of a number in a sorted list of arbitrary naturals. One way is to hash the frequency of divisors of each i we add to the search structure of A[i]. But first consider i as j and add to the result the count of divisors q that already exist in the hash map.

JavaScript code with brute force testing at the end:

function gcd(a, b){
  return b ? gcd(b, a % b) : a;
}


function getQ(X, j){
  return X / gcd(X, j);
}


function addDivisors(n, map){
  let m = 1;
    
  while (m*m <= n){
    if (n % m == 0){
      map[m] = -~map[m];
      
      const l = n / m;
      
      if (l != m)
        map[l] = -~map[l];
    }
    
    m += 1;
  }
}


function f(A, X){
  const Ais = {};
  let result = 0;
  
  for (let j=1; j<A.length; j++){
    if (A[j] == A[0])
      result += 1;

    // Search
    if (Ais.hasOwnProperty(A[j])){
      const q = getQ(X, j);

      result += Ais[A[j]][q] || 0;
    
    // Initialise this value's
    // search structure
    } else {
      Ais[A[j]] = {};
    }
    
    // Add divisors for j
    addDivisors(j, Ais[A[j]]);
  }
  
  return result;
}


function bruteForce(A, X){
  let result = 0;
  
  for (let j=1; j<A.length; j++){
    for (let i=0; i<j; i++){
      if (A[i] == A[j] && (i*j % X) == 0)
        result += 1;
    }
  }
  
  return result;
}


var numTests = 1000;
var n = 100;
var m = 50;
var x = 100;

for (let i=0; i<numTests; i++){
  const A = [];

  for (let j=0; j<n; j++)
    A.push(Math.ceil(Math.random() * m));
    
  const X = Math.ceil(Math.random() * x);
  
  const _brute = bruteForce(A, X);
  const _f = f(A, X);

  if (_brute != _f){
    console.log("Mismatch!");
    console.log(X, JSON.stringify(A));
    console.log(_brute, _f);
    break;
  }
}

console.log("Done testing.")