Count Coprime Subsequences
Practice
2.8 (4 votes)
Combinatorics
Dynamic programming
Basic programming
Number theory
Math
Inclusion Exclusion
Problem
60% Success 412 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 \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\)
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.
Code Editor
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Submissions
Please login to view your submissions
Similar Problems
Points:30
5 votes
Tags:
ApprovedDepth First SearchInclusion ExclusionInclusion exclusion principleMathMediumMobius Function
Points:30
11 votes
Tags:
AlgorithmsApprovedMathMediumOpen
Points:30
1 votes
Tags:
CombinatoricsInclusion-ExclusionMathMedium
Editorial
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor