Proficient.
Put your skills to the test.

Problem summary

Print all positive integers at most N that can be expressed as a sum of copies of A and B. Either summand may be used any nonnegative number of times.

Constraints

0 < A < B < N < 50,000.

Worked example

An independently prepared example for this explanation.

4 5 11

4
5
8
9
10

Solution analysis

1. Use reachable[s] to record whether s can be made. Mark zero reachable as an empty intermediate sum, even though zero is not an output.
2. For each s from 1 through N, s is reachable if s−A or s−B is a nonnegative reachable sum. These predecessors are smaller than s, so an increasing scan has already decided them.
3. With A = 4 and B = 5, the first reachable sums are 4 and 5. They then generate 8, 9 and 10; no predecessor makes 11. Print a number immediately after computing its reachability to obtain sorted output.

Why it works

A reachable predecessor gives a valid sum after appending A or B. Conversely, any positive valid sum has a final summand A or B; deleting it gives one of the predecessors tested by the recurrence. Induction on s establishes every entry, hence all and only required numbers are printed.

Watch out. Do not print the seed zero. Allow repeated copies and the use of only one type of summand.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int a,b,limit;
    cin>>a>>b>>limit;
    vector<bool>reachable(limit+1,false);
    reachable[0]=true;
    for(int sum=1;sum<=limit;++sum){
        // Removing the last summand leaves a smaller reachable sum.
        reachable[sum]=(sum>=a&&reachable[sum-a])||(sum>=b&&reachable[sum-b]);
        if(reachable[sum]){
            cout<<sum<<'\n';
        }
    }
}