Count Attack Vectors by Divisor Range
Visa● MediumFULLTIMEOAProblem statement
An attack vector for an integer array keys is a triple (i, j, x) such that both keys[i] and keys[j] are divisible by x.
The pair (i, j) is ordered, and i may equal j. For each inclusive query [left, right], return the total number of attack vectors whose divisor satisfies left <= x <= right.
Return one 64-bit answer per query, in the original query order.
Function
countAttackVectors(keys: int[], queries: int[][]) → long[]Examples
Example 1
keys = [6,9,10]queries = [[2,3],[9,10]]return = [8,2]For divisors 2 and 3, two keys are divisible by each divisor, so each contributes 2^2 = 4. Divisors 9 and 10 each divide one key and contribute one vector.
Example 2
keys = [1,2,4]queries = [[1,4]]return = [14]The counts of divisible keys for divisors 1 through 4 are 3, 2, 0, and 1, giving 9 + 4 + 0 + 1 = 14.
Constraints
1 <= keys.length <= 1000001 <= keys[i] <= 1000001 <= queries.length <= 100000- Each query has two values with
1 <= left <= right <= 100000. - Each answer fits in a signed 64-bit integer.