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 0i<N1, 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 109+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 109+7.

Constraints:

  • 1T10
  • 1N105
  • 1arr[i]105
Time Limit: 5
Memory Limit: 256
Source Limit:
Explanation
  • In first test case, every non-empty subsequence is co-prime, thus 241=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

?