RIO3 - Editorial

PROBLEM LINK:

Practice

Author: Vishal Khopkar

DIFFICULTY:

EASY

PREREQUISITES:

None

PROBLEM:

We are given two numbers i and j and a number ‘n’, and our aim is to find all numbers less than or equal to n which are either i or j or obtained from the sum of the given numbers.
For example,

n=20

i=2, j=5

The output will contain 2, 5, 2+5=7, 7+2=9, 9+2=11, 7+5=12, 11+2=13, 9+5=14, 13+2=15, 11+5=16, 15+2=17, 13+5=18, 14+5=19, 15+5=20

EXPLANATION:

If the two numbers i, j are co-prime, then we need to find all numbers upto their product because all numbers ahead would anyways be a part of the output. Similarly, if one number is a multiple of the other, the solution contains all the multiples of the smaller number upto ‘n’. In this way, you need to find ways so that you can get to the solution faster.

SOLUTION

Solution

//