Handsome Number Editorial

Can anyone provide the Editorial for https://www.codechef.com/NCL2017/problems/NCL1706

Here is the Decription of how I solved this problem using diophantine equation for 3 variables.
let’s countofFive be Number of 5’s that will be in answer,CountOfTwo be Number of 2’s that will be in answer and CountOfThree be Number of 3’s that will be in answer.Now CountOfThree must be divisible by 10,CountOfTwo must be divisible by 15,CountOfFive must be divisible by 6.So I came up with diophantine equation…
6CountOfFive+15CountOfTwo+10*CountOfThree=n
Now solve for CountOfThree,CountOfTwo,CountOfFive.Now first print 6 multipled byCountOfFive times no.5,10 Multiplied by CountOfThree times no.3,15 multiplie by CountOfTwo times number 2.This Will be required answer to the problem.Hope You get this.

4 Likes

Can anyone provide some good links that explain how to solve linear diophantine equations ?

@pankajkhan Here are some usefull questions and learning source of linear diophantine equation.

Learning source:-

Questions:-

2 Likes

https://www.codechef.com/viewsolution/12968444

thanks for the link

how you solved for the equation 6CountOfFive+15CountOfTwo+10*CountOfThree=n can you explain

Ran a loop of “i” from 0 to n/15 and second loop of “j” from 0 to n/10 now leftover is (n-i15-j10) and let it be sum,now check if sum greater than or equal to 0 and if its divisible by 6. if it is then you have got your answer
Now i is the required count of 2 multiply it by 15,j is required count of 3 multiply it by 10 and sum is required count of 5.Now print sum times 5 then j times 3 and i times 2 that the required answer.Here is the solution link for reference. Solution Link

3 Likes