Count Coprime Subsequences

2.8

4 votes
Combinatorics, Dynamic Programming, Basic Programming, Number theory, Math, Inclusion-exclusion
Problem

A sequence \(S\) of length \(N\) is called co-prime sequence if \(GCD(S[i], S[i + 1]) = 1\) for \(0 \le i < N - 1\), i.e. every adjacent element is co-prime, any sequence of length \(1\) is a co-prime sequence.

Given an Array \(arr\) of length \(N\), find the number of non-empty co-prime subsequences of this array, modulo \(10^9+7\).

Input Format:

  • First line contains an integer \(T\) denoting the number of test cases.
  • First line of each testcase contains an integer \(N\) denoting length of \(arr\).
  • Next line contains \(N \) space-seperated integer, denoting the elements of \(arr\).

Output Format:

  • For each testcase, In a single line, print the number of non-empty co-prime subsequence of the array, modulo \(10^9+7\).

Constraints:

  • \(1 \le T \le 10\)
  • \(1 \le N \le 10^5\)
  • \(1 \le arr[i] \le 10^5\)
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation
  • In first test case, every non-empty subsequence is co-prime, thus \(2^4 - 1 = 15\) subsequences.
  • In second test case, only length 1 subsequences ie. 5 subsequences are co-prime, every other subsequence has common factor of \(2 \) between adjacent elements.
  • In fourth test case, coprime subsequences are all length 1 subsequences and \([1, 2], [1, 4], [1, 6], [1, 8], [1, 10], [1, 12]\), thus \(7 + 6 = 13\) subsequences.
  • In fifth test case, the number of co-prime subsequences are, \(8\) (1-length), then \([1, 2]\) 6 times, \([2, 1]\) 6 times and \([1,2,1]\) 6 times, and \([1, 1]\), thus \(8 + 6 + 6 + 6 + 1 = 27\) subsequences.
Editor Image

?