Codeforces Round 450 – Problem D

By | December 16, 2017

Problem D

Statement :You are given two numbers ‘x’ and ‘y’ , we have to find the number of sequences of all lengths whose gcd is ‘x’ and whose sum is ‘y’.

i.e. \sum a_{i} = y,    and    gcd (a_{0},a_{1},a_{2}, ----- , a_{n}) = y

(Link to the problem)

Solution :

Now first thing that comes to mind is if  ‘y’ is not divided by ‘x’, then gcd (a[0],a[1],a[2],—–a[n]) can never be ‘x’ whose sum is ‘y’.

Suppose there exists ‘n’ numbers whose gcd is ‘x’.

then we can take ‘x’ common from all the numbers.

Since,             \sum a_{i} = y,

then    (\sum x*(a_{i}/x) = y)   --->   (x*\sum (a_{i}/x) = y)

So it shows that , for ‘y’ to be sum of all a[i] whose gcd is ‘x’, ‘y’ should be divisible by ‘x’.

So,

1) if ‘y’ is not divisible by ‘x’, means answer is ‘0’ because there doesn’t exists any sequence whose gcd can be ‘x’ and sum = ‘y’.

2) What will happen if ‘y’ is divisible by ‘x’ ?

In that case , we need to find the sequences of elements whose sum is ‘y’ and gcd is ‘x’.

Now if gcd is ‘x’, we can take ‘x’ common from all the elements and now all the elements are coprime. and their sum is ‘y/x’.

Let  y = ‘y/x’

What does this mean ?

(\sum (a_{i}) = y/x) 

where $latex(a_{i})&s=1$ are coprime with each other.

Now, how can we approach this problem.

The problem comes down to a small problem where we have to find number of sequences whose sum is ‘y’ and all numbers in sequence are co-prime with each other.

Now we can divide the problem into two parts:-

1) Number of sequences whose sum is ‘y’.

2) How many sequences are there in those which have all elements of those sequences as co-prime with each other?

 

Now, if we look at first problem , it is similar to star and bars problem.

Suppose we have been given ‘y’ stars and ‘y-1’ number of bars.

* * * || * * * * *| * * * * || * * * *

Now, some considerations we have in this:

1)  we have ‘y-1’ places to put bars that will divide the stars.

2) Each bar can be placed in any of these positions.

3) If we place each bar in different positions , at end between every two bars, there will be 1 star. So, it corresponds to ‘y’ elements where each element is 1 and sum is ‘y’.

4) Now , if you place any two bars together, and more than 1 element between any two bars, it means we have some element whose value is more than 1 and number of different elements will be less than ‘y’ because two bars are placed together so one of the bar is not separating any of two stars, so that bar is not useful, so we can consider that bar as not present. So finally we can consider as ‘y-2’ bars to be placed at ‘y-1’ places.

5) Similarly, we can consider ‘y-2’, ‘y-3’, —-‘1’ bars to be placed when 2,3,4,–y-2 bars to be placed together.

6) Similarly, if we find no of ways to place bars in this stars collection, we will get no of sequences whose sum = ‘y’.

so in how many ways you can put bars in this stars group.

for 0 bar = 1 way

for 1 bar = y-1 ways

for 2 bars = \binom{y-1}{2}

for 3 bars = \binom{y-1}{3}

—–

for y-1 bars = \binom{y-1}{y-1}

So the sum of these will represent the sequences whose sum is ‘y’.

\binom{y-1}{0} + \binom{y-1}{1}  + \binom{y-1}{2} + \binom{y-1}{3} +----- + \binom{y-1}{y-3} + \binom{y-1}{y-2} + \binom{y-1}{y-1}

This is nothing but the binomial expansion of

(1+x)^{(y-1)} .

if we put (x==1) , then sum is

2^{(y-1)} .

You can read more about star and bars problem here.

https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)

Now, comes the second problem, what are those sequences whose elements are not co-prime ?

1) Now, we need to find what possible gcd for the sequences be possible.

the gcd can be all the factors of the number ‘y’.

Now , we need to find all the factors of ‘y’.

Which we can easily find by iterating from ‘1’ to sqrt(y) and saving all the numbers which divide ‘y’ as well as ‘y/factor’ because half of factors lie on left side of sqrt(y) and half on right.

We need to store unique factors.

So, if ‘y’ is a perfect square , include its sqrt(y) only once.

2) Now our problem reduce to a smaller problem.

Since we have all the factors of ‘y’, we need to find those sequences whose gcd is that factor and sum is ‘y’.

Which is a smaller problem of the original problem.

But we need to subtract this from the original number of sequences whose sum is ‘y’.

3) We need to calculate the same thing again for smaller values.

Now , this looks similar to a recursive problem.

Solve(x) = 2^{x-1} -   \sum  (solve(x/factor[i]) = y/x )

We can add memoization to this recurrence.

But, since we have ‘y’ ranging till 10^{9} , it means we cannot store it in an array, we will store it in a map.

So,

Final algorithm becomes :-

1) Find if ‘x’ divide ‘y’, if no, answer is ‘0’.

2) If ‘yes’,  divide ‘y’ by ‘x’. i.e. y = y/x

3) Now find all the sequences whose sum is ‘y’ which is given 2^{x-1} .

4) Remove all the sequences whose sum is ‘y’ but whose gcd is >1.

5) This can be done by removing all those subsequences whose gcd is one of the factor of ‘y’.

So, solve the original problem for ‘y/factor[i]’ and repeat this for all factors of ‘y’.

and subtract from the original number of sequences.

 

Now the complexity is :-

1) finding the factors for a number y/x -> sqrt(y/x)

2) total count of numbers that we are considering here.

Since, for initial number ‘y/x’, we can have a maximum of around (2*cuberoot(y/x) + 1) factors.

and all the possible numbers that are factor of initial number will only be calculated during the whole calculations so total complexity be equal to (2*(cuberoot(y/x))*(sqrt(y/x))

i.e.  (y/x)^{\frac{1}{3}}*(y/x)^\frac{1}{2} = (y/x)^{\frac{5}{6}}

3) Also, since we are using map to store the numbers to retrieve them we need to get them. We can use unordered map to get O(1) retrieval.

So, complexity is :-

Overall Time Complexity —-> O((y/x)^{\frac{1}{3}}*(y/x)^\frac{1}{2} = (y/x)^{\frac{5}{6}})

Overall Space Complexity —-> O((y/x)^{\frac{1}{3}}*(y/x)^\frac{1}{2} = (y/x)^{\frac{5}{6}}) {for factor array and map}

 

2 thoughts on “Codeforces Round 450 – Problem D

  1. Abhishek Rawat

    Couldn’t get this one in the contest. Rating would’ve gotten sky highed otherwise. A good editorial for D , Waiting for E now. 😉

    Reply

Leave a Reply

Your email address will not be published. Required fields are marked *