Find sum of gcd of all subsequence of size K from 1 to n (in O(nlogn))

Asked Sep 14 '19 at 06:47

Active Sep 14 '19 at 06:47

Viewed 195 times

Suppose a[]={1,2,3,4,5} and K=3

Sum of gcd of all subsequence of size k = gcd(1,2,3)+gcd(1,2,4)+gcd(1,2,5)+gcd(1,3,4)+gcd(1,3,5)+gcd(1,4,5)+gcd(2,3,4)+gcd(2,3,5)+gcd(2,4,5)+gcd(3,4,5).

How can we find this for different values of k?

2<=k<=100000
1<=n<=100000

asked Sep 14 '19 at 06:47

Saurabh Yadav

Start by coding a routine that generates all subsequence of `a` and the rest is one loop around it with a sum. – PilouPili Sep 14 '19 at 11:59
but the time complexity to find subsequence is (O(n^2)) – Saurabh Yadav Sep 15 '19 at 14:41
Can you give the pseudo code? – Saurabh Yadav Sep 15 '19 at 14:42
https://stackoverflow.com/questions/4555565/generate-all-subsets-of-size-k-from-a-set and for the gcd part https://www.geeksforgeeks.org/gcd-two-array-numbers/ – PilouPili Sep 15 '19 at 15:56
As for complexity since the size of the subsequence is n!/(k! (n-k)!) I hardly see how you could achieve O(n log n) with generating all subsequence as in your example. – PilouPili Sep 15 '19 at 15:59

Find sum of gcd of all subsequence of size K from 1 to n (in O(nlogn))

0 Answers0