Base-p Numbers
National Olympiad — Municipal round
Submission name: pnum.cpp
Problem summary
List all positive integers at most n whose representation in base p contains only digits 0 and 1. Print their decimal values in increasing order.
Input
Two integers n and p.
Output
One qualifying decimal integer per line.
Constraints
2 ≤ n ≤ 100,000,000; 2 ≤ p ≤ 255.
Worked example
An independently prepared example for this explanation.
Input
10 3
Output
1 3 4 9 10
Solution analysis
- In base 2, every integer has only 0/1 digits, so print 1 through n directly.
- For p > 2, start from the one-digit number 1.
- Appending 0 to a base-p representation changes x to x·p; appending 1 changes it to x·p+1.
- A FIFO queue visits digit lengths in order, and within a length visits numbers in increasing order. Enqueue only children at most n.
Why it works
Every valid representation begins with 1, and removing its last digit gives another valid representation. Thus the generation tree contains exactly the wanted numbers. Children of smaller parents precede those of larger parents, so the queue order is increasing.
Watch out. Output itself may be huge for p=2. Do not queue all those values; print them directly.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<queue>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n,p;
cin>>n>>p;
if(p==2){
for(long long x=1;x<=n;++x){
cout<<x<<'\n';
}
return 0;
}
queue<long long>q;
q.push(1);
while(!q.empty()){
long long x=q.front();
q.pop();
cout<<x<<'\n';
// The two children append base-p digits 0 and 1.
if(x*p<=n){
q.push(x*p);
}
if(x*p+1<=n){
q.push(x*p+1);
}
}
}