Prime-Weighted Representation
National Olympiad — Municipal round
Submission name: prime.cpp
Problem summary
A binary string a₁…aₖ represents the number Σ aᵢpᵢ, where pᵢ is the i-th prime (2,3,5,…). Convert it to decimal.
Input
One binary string ending in 1.
Output
The represented integer.
Constraints
String length ≤ 3000; the represented integer is at least 2.
Worked example
An independently prepared example for this explanation.
Input
1011
Output
14
Solution analysis
- Generate successive primes by trial division using previously found primes up to the square root.
- When the i-th prime is found, add it if the i-th input character is 1.
Why it works
Trial division identifies each prime in increasing order. Each binary coefficient then contributes exactly its specified prime weight.
Complexity: O(P√P) conservative time and O(k) memory, where P is the k-th prime; k≤3000.
Watch out. The leftmost bit weights 2, not the largest prime. This is not binary positional notation.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Trial division identifies each prime in increasing order. Each binary coefficient then
// contributes exactly its specified prime weight.
#include<iostream>
#include<vector>
#include<string>
using namespace std;
int main(){
string s;
cin>>s;
vector<int>primes;
long long answer=0;
for(int x=2;primes.size()<s.size();x++){
bool ok=true;
for(int p:primes){
if(p*p>x){
break;
}
if(x%p==0){
ok=false;
break;
}
}
if(ok){
if(s[primes.size()]=='1'){
answer+=x;
}
primes.push_back(x);
}
}
cout<<answer<<'\n';
}