Positive Two-Coin Equation
National Olympiad — Municipal round (2022 season)
Submission name: equation.cpp
Problem summary
Count k∈[1,L] that cannot equal ax+by for positive integers x,y.
Input
a b L.
Output
The number of unrepresentable k.
Constraints
1≤a,b<1000; 1≤L<100000.
Worked example
Input and output for the worked example discussed below.
Input
2 3 7
Output
5
Solution analysis
- Positive coefficients require one copy of each denomination, so initialize reachability at a+b rather than zero.
- Scan totals upwards, adding a or b from reachable totals. Positive increments make every transition go to a later state, so one pass suffices.
- For2,3,7 only5 and7 are reachable. Values1,2,3,4,6 are not, giving5. If a+b>L, all L values fail.
Why it works
Every reachable state includes the mandatory copies. Conversely any valid representation can be built by adding its remaining copies from a+b.
Complexity: O(L) time and O(L) space with two transitions per total.
Watch out. Starting at zero would incorrectly permit a zero coefficient.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
// Every reachable state includes the mandatory copies.
int main(){
int a,b,limit;
cin>>a>>b>>limit;
vector<bool>possible(limit+1,false);
if(a+b<=limit){
possible[a+b]=true;
}
for(int x=1;x<=limit;x++){
if(!possible[x]){
continue;
}
if(x+a<=limit){
possible[x+a]=true;
}
if(x+b<=limit){
possible[x+b]=true;
}
}
int answer=0;
for(int x=1;x<=limit;x++){
answer+=!possible[x];
}
cout<<answer<<'\n';
}