Count Coprime Subsequences
Practice
2.8 (4 votes)
Combinatorics
Dynamic programming
Basic programming
Number theory
Math
Inclusion Exclusion
Problem
60% Success 432 Attempts 30 Points 5s Time Limit 256MB Memory 1024 KB Max Code

A sequence S of length N is called co-prime sequence if GCD(S[i],S[i+1])=1 for 0≤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 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:

  • 1≤T≤10
  • 1≤N≤105
  • 1≤arr[i]≤105
Sample Input
5
4
1 1 1 1
5
2 4 6 8 10
6
1 2 3 4 5 6
7
1 2 4 6 8 10 12
8
1 2 2 2 2 2 2 1
Sample Output
15
5
43
13
27
Explanation
  • In first test case, every non-empty subsequence is co-prime, thus 24−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.
Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Submissions
Please login to view your submissions
Similar Problems
1.GCD on a tree
Points:30
5 votes
Tags:
ApprovedDepth First SearchInclusion ExclusionInclusion exclusion principleMathMediumMobius Function
2.Equivalent Strings 2
Points:50
1 votes
Tags:
AlgorithmsOpenApprovedHard
3.Bob and consulting sessions
Points:30
40 votes
Tags:
CombinatoricsInclusion-exclusionAlgorithmsMath
Editorial

Login to unlock the editorial