How should I practice Great Subsequences?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft online assessment problems in FastPrep.

Is Great Subsequences associated with Microsoft?

FastPrep tags this as a Microsoft coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Dynamic Programming

Great Subsequences

Learn this problem

● HardMicrosoftOA

See Microsoft hiring insights

Problem statement

You are given an array A of length N.

A subsequence is said to be great if the GCD of the elements of the subsequence is greater than 1. An empty subsequence is not a great subsequence.

You are given Q queries and in each query you are given two integers X and Y (1 <= X <= N, 1 <= Y <= 10^5). You need to replace the X^th element in A with Y. In other words, set A[X] = Y. Let the answer to each query be the number of great subsequences.

Let's define an array S containing the answer to each query.

Find the sum of S. Since the answer can be large, return it modulo 10^9 + 7.

Input Format

The first line contains an integer, N, denoting the number of elements in A.

Each line i of the N subsequent lines (where 1 <= i <= N) contains an integer describing A[i].

The next line contains an integer, Q, denoting the number of rows in queries.

The next line contains an integer, P, denoting the number of columns in queries.

Each line i of the Q subsequent lines (where 1 <= i <= Q) contains P space separated integers each describing the row queries[i].

Function

greatSubsequences(A: int[], queries: int[][]) → int

Examples

Example 1

A = [1, 2]queries = [[1, 2]]return = 3

Given N=2, A=[1,2], Q=1, P=2, queries=[(1,2)]

After the first query, the subsequences are [2, 2], [2] and [2]. All of these GCD is more than 1. So, answer is 3.

Example 2

A = [1, 2, 3]queries = [[1, 3], [2, 3]]return = 11

Given N=3, A=[1,2,3], Q=2, P=2, queries=[(1,3), (2,3)]

After query 1, A become [3,2,3], then good subsequences are [2],[3],[3],[3,3].

After query 2, A become [3,3,3], then good subsequences are [3],[3],[3],[3,3],[3,3],[3,3],[3,3,3]

So, answer is 4+7=11.

Example 3

A = [2, 2, 2, 2, 2]queries = [[1, 1], [2, 1]]return = 22

Given N=5, A=[2,2,2,2,2], Q=2, P=2, queries=[(1,1), (2,1)]

After query 1, A = [1,2,2,2,2], then total number of good subsequences is 15.

After query 2, total number of good sequence is 7.

Hence, the answer is 15+7=22.

Constraints

1 <= N <= 10^5

1 <= A[i] <= 10^5

1 <= Q <= 10^5

2 <= P <= 2

1 <= queries[i][j] <= 10^5