Square of a Million-Digit Repunit
National Olympiad — National round (2009 season)
Submission name: ones.cpp
Problem summary
Print the exact square of the integer consisting of n ones.
Input
One integer n.
Output
The complete decimal square.
Constraints
1 ≤ n ≤1000000.
Worked example
Input and output for the worked example discussed below.
Input
9
Output
12345678987654321
Solution analysis
- Before carrying, product position k receives one contribution for every digit-position pair i+j=k. The coefficient counts form1,2,…,n−1,n,n−1,…,2,1.
- Generate coefficients from the units upward. Add incoming carry, emit the remainder modulo10, and forward the quotient. This remains valid even when a coefficient exceeds9.
- For n=9 no carry is needed and the familiar12345678987654321 appears. For n≥10 the coefficients are counts rather than digits, so carry propagation is essential. Reverse the emitted digits before printing.
Why it works
The triangular coefficients count every term of the product’s digit convolution. Standard carry propagation preserves its represented value while producing valid decimal digits. Reversal therefore yields the exact square.
Complexity: O(n) time and O(n) output space.
Watch out. Do not print the triangle literally for n≥10 or attempt quadratic big-integer multiplication for a million digits.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
cin>>n;
string reversed;
reversed.reserve(2*n);
int carry=0;
for(int place=0;place<2*n-1;place++){
// Count digit pairs contributing to this decimal position.
int coefficient=min(place+1,2*n-1-place);
int value=coefficient+carry;
reversed+=char('0'+value%10);
carry=value/10;
}
while(carry>0){
reversed+=char('0'+carry%10);
carry/=10;
}
reverse(reversed.begin(),reversed.end());
cout<<reversed<<'\n';
}