求下标能被另一个数x整除的数对的乘积

Question

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

Array size <= 10^5

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

有更好的方法吗?

Answer 1

首先，在迭代时为每个不同的A[i]存储单独的搜索结构。

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

设X / j为某分数。因为i是一个整数，所以k的形式应该是m * least_common_multiple(X, j) / X, where m is natural。

示例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

示例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

接下来，我将考虑如何有效地查询任意自然数排序列表中某一数字的倍数个数。一种方法是对我们添加到A[i]的搜索结构中的每个i的除数频率进行哈希。但首先将i视为j，并将哈希映射中已经存在的除数q的计数添加到结果中。

JavaScript代码与暴力测试在最后:

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.")

Answer 2

以防万一，如果有人需要这个答案的java版本- https://stackoverflow.com/a/69690416/19325755解释已在该答案中提供。

我花了很多时间来理解javascript代码，所以我认为那些熟悉java的人可以参考这篇文章来更好地理解。

import java.util.HashMap;
public class ThisProblem {
public static void main(String[] args) {
int t = 1000;
int n = 100;
int m = 50;
int x = 100;
for(int i = 0; i<t; i++) {
int[] A = new int[n];
for(int j = 0; j<n; j++) {
A[j] = ((int)Math.random()*m)+1;
}
int X = ((int)Math.random()*x)+1;
int optR = createMaps(A, X);
int brute = bruteForce(A, X);
if(optR != brute) {
System.out.println("Wrong Answer");
break;
}
}
System.out.println("Test Completed");
}
public static int bruteForce(int[] A, int X) {
int result = 0;
int n = A.length;
for(int i = 1; i<n; i++) {
for(int j = 0; j<i; j++) {
if(A[i] == A[j] && (i*j)%X == 0)
result++;
}
}
return result;
}
public static int gcd(int a, int b) {
return b==0 ? a : gcd(b, a%b);
}
public static int getQ(int X, int j) {
return X/gcd(X, j);
}
public static void addDivisors(int n, HashMap<Integer, Integer> map) {
int m = 1;
while(m*m <= n) {
if(n%m == 0) {
map.put(m, map.getOrDefault(m, 0)+1);
int l = n/m;
if(l != m) {
map.put(l, map.getOrDefault(l, 0)+1);
}
}
m++;
}
}
public static int createMaps(int[] A, int X) {
int result = 0;
HashMap<Integer, HashMap<Integer, Integer>> contentsOfA = new HashMap<>();
int n = A.length;
for(int i = 1; i<n; i++) {
if(A[i] == A[0])
result++;
if(contentsOfA.containsKey(A[i])) {
int q = getQ(X, i);
result += contentsOfA.get(A[i]).getOrDefault(q, 0);
} else {
contentsOfA.put(A[i], new HashMap<>());
}
addDivisors(i, contentsOfA.get(A[i]));
}
return result;
}

}