Problem Link:
Difficulty:
SIMPLE
Pre-requisites:
Dynamic Programming
Problem:
Given a sequences of N positive numbers A[0], A[1], …, A[N-1], find how many subsequences of the integers are possible, for which the following procedure terminates in all integers equal to 1. The procedure is to take two unequal numbers, and replace the larger with the difference of the two. The procedure ends when all numbers become equal.
Explanation:
Given a particular sequence of integers, the final number you end up with is the GCD of the numbers. This is because, at each step, the GCD remains invariant, and when all numbers are equal, their GCD will be the number itself.
The question then reduces to finding the number of subsequences of the sequence A, whose gcd is 1.
For this, we go through the numbers A[0], A[1], …, in order, and at each step make a choice as to whether to pick it, or not. We then have to also ask if at the end, the GCD will be 1, and so we recursively pass on the information of our current gcd.
Thus, we can define the function:
f(pos, current_gcd) = f(pos+1, current_gcd) + f(pos+1, gcd(current_gcd, A[pos]))
with the base cases as
f(N, 1) = 1, f(N, k) = 0 for k > 1,
f(pos, 1) = 2^(N-pos) to speed up calculation.
Finally, the answer we require is sum(pos = 0 to N-1) f(pos+1, A[pos]).
The above procedure needs to be memoized in order to work in time. Since A[i] <= 10^4, we get that current_gcd <= 10^4. In particular, the current_gcd will be a divisor of some A[i], hence the total number of states will be atmost N * (total number of divisors of A[i]). This is small enough to work in time, (certainly less than N * 10^4 per testcase).
Setter’s Solution:
Can be found here
Tester’s Solution:
Can be found here
