Distant Decimal Digits
Национална олимпиада - Областен кръг 2026
Submission name: period.cpp
Problem summary
Print decimal digits m through n, counted from one after the decimal point, in the expansion of 1/a. Preserve zeros, including those after a terminating expansion.
Input
a m n.
Output
The requested consecutive digits.
Constraints
2 ≤ a ≤ 10^6; 1 ≤ m ≤ n ≤ 10^9; n−m ≤ 100.
Worked example
The worked example illustrates the rule described in the analysis.
Input
22 1 6
Output
045454
Solution analysis
- Long division maintains a remainder r. Its next digit is floor(10r/a), and its next remainder is 10r mod a.
- Immediately before digit m, the remainder is 10^(m−1) mod a. Compute it with binary exponentiation instead of generating a billion earlier digits.
- Generate the requested at most 101 digits by ordinary long division. For a=22, the remainder sequence produces 0,4,5,4,5,4, giving 045454.
Why it works
Initially the remainder is 1. Each long-division step multiplies it by ten modulo a, proving the exponent formula. Starting with that remainder therefore generates exactly the requested suffix of the expansion.
Watch out. Do not discard leading zeros or stop at a zero remainder. Use exponent m−1, not m; intermediate products require long long.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Initially the remainder is 1. Each long-division step multiplies it by ten modulo a,
// proving the exponent formula.
#include<algorithm>
#include<array>
#include<cstdint>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
using namespace std;
long long powerMod(long long base,long long exponent,long long divisor){
long long result=1;
while(exponent>0){
if(exponent%2!=0){
result=result*base%divisor;
}
base=base*base%divisor;
exponent/=2;
}
return result;
}
int main(){
long long divisor,first,last;
cin>>divisor>>first>>last;
long long remainder=powerMod(10,first-1,divisor);
for(long long position=first;position<=last;++position){
remainder*=10;
cout<<remainder/divisor;
remainder%=divisor;
}
cout<<'\n';
}