Great Subsequences

Problem Overview

• Given an array A, a "great" subsequence is non-empty with GCD > 1; after each update A[X]=Y, count great subsequences for that state.
• Input: N, initial A, and Q queries (1 ≤ X ≤ N, 1 ≤ Y ≤ 1e5); output the sum of these counts modulo 1e9+7.
• Constraints: N, Q ≤ 1e5; A[i], Y ≤ 1e5; 1-based indices.
• Number theory and dynamic array updates context, relevant to data processing scenarios.
• Asked in Microsoft interviews; a coding interview problem and interview question.