A Slice of the Concatenated Positive Integers
National Olympiad — Regional round (2025 season)
Submission name: long.cpp
Problem summary
Concatenate 1,2,3,… . Print digits n…p, the product modulo d of nonzero digits n…m, and digit frequencies in n…m.
Input
n p m d.
Output
Three lines: requested substring; product remainder; ten counts for digits 0…9.
Constraints
1≤n≤p≤m<1000000; p−n≤50; 2≤d≤100.
Worked example
Input and output for the worked example discussed below.
Input
7 14 16 17
Output
78910111 5 1 5 1 0 0 0 0 1 1 1
Solution analysis
- Generate positive integers as digit strings, tracking a 1-based position counter. Stop at m rather than storing the entire million-digit concatenation.
- At positions at least n, count each digit and multiply it into the residue only if nonzero. Also append it to the short output if the position is at most p; at most 51 characters are retained.
- Positions 7…16 are 7891011121. The requested slice is 78910111. Ignoring zero, the product is 1008, with remainder 5 modulo 17, and its digit counts give the final output line.
Why it works
Sequential generation gives the defining concatenation. Position checks select exactly the requested intervals, and the counters and modular product retain their meanings after every processed digit.
Watch out. Zero is counted in frequencies but excluded from the product. Positions start at 1; an empty product of nonzero digits is 1.
Commented C++17 solution
An independently written complete program with standard headers.
#include<array>
#include<iostream>
#include<string>
using namespace std;
int main(){
int first;
int shortEnd;
int last;
int divisor;
cin>>first>>shortEnd>>last>>divisor;
array<int,10>frequency{};
string answer;
int product=1;
int position=0;
for(int number=1;position<last;number++){
for(char character:to_string(number)){
position++;
if(position>last){
break;
}
if(position<first){
continue;
}
int digit=character-'0';
frequency[digit]++;
// Count zeros but omit them from the product.
if(digit!=0){
product=product*digit%divisor;
}
if(position<=shortEnd){
answer+=character;
}
}
}
cout<<answer<<'\n'<<product<<'\n';
for(int digit=0;digit<10;digit++){
if(digit>0){
cout<<' ';
}
cout<<frequency[digit];
}
cout<<'\n';
}