Show problems as
Classic problem #3901HardArrayMathSegment TreeNumber Theory

Good Subsequence Queries

Real-world version: Matched Pairs After Each Rewrite
Tracked in this browser only
Read Good Subsequence Queries on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Register values are given as nums, along with a target p.

Two positions i < j form a matched pair when nums[i] * nums[j] divides evenly by p.

Each entry of queries is [ind, val] and rewrites nums[ind] to val, a change that stays for every later query. Count the matched pairs after each rewrite, and return the total of those counts modulo 10^9 + 7.

Examples

Example 1

Input
nums = [6, 10, 15, 4, 9], p = 12, queries = [[0, 8], [2, 6], [4, 3]]
Output
14

Each rewrite is counted after it lands and the changes carry forward, so the three counts are added together.

Example 2

Input
nums = [1, 1], p = 1, queries = [[0, 1]]
Output
1

Every product divides evenly by one, so the single pair always matches and the one rewrite reports one.

Example 3

Input
nums = [3, 5, 7, 11], p = 2, queries = [[0, 2], [1, 4]]
Output
8

The values start out all odd, so no product is even. The first rewrite puts a 2 in place and still leaves no pair, since one even value is not enough on its own; the second puts a 4 in, and that pair matches.

Constraints

  • 2 <= nums.length <= 5 * 10^4
  • 1 <= nums[i] <= 5 * 10^4
  • 1 <= p <= 5 * 10^4
  • 1 <= queries.length <= 5 * 10^4
  • queries[i].length == 2
  • 0 <= queries[i][0] <= nums.length - 1
  • 1 <= queries[i][1] <= 5 * 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def count_good_subseq(nums: list[int], p: int, queries: list[list[int]]) -> int:
Java
public int countGoodSubseq(int[] nums, int p, int[][] queries)

More on the same topics