The k-th Digit of a Power
National Olympiad — Regional round (2022 season)
Submission name: kdigit.cpp
Problem summary
For each test, find the k-th decimal digit from the right of a^b.
Input
t, then t triples a b k.
Output
The requested digit for each test, one per line.
Constraints
1 ≤ t ≤ 100; 1 ≤ a,b ≤ 10^18; 1 ≤ k ≤ 1000; the requested digit exists.
Worked example
An independently prepared example for this explanation.
Input
1 42 7 7
Output
9
Solution analysis
- Only the last k digits can affect the requested digit. Work modulo 10^(4*ceil(k/4)), representing the residue in little-endian blocks of four decimal digits, base 10000.
- Use binary exponentiation. Multiply block arrays by ordinary convolution, discarding every block beyond the retained length, and normalize carries in base 10000. Retaining a few extra decimal digits causes no problem: the k-th digit still lies within the residue.
- For 42^7=230539333248 and k=7, the retained final blocks are 3248,3933,... . Position seven lies in block one at its hundreds digit, giving 9. With k=1, only the units digit of the first block is needed.
Why it works
For any modulus B^L, products of residues equal the residue of the product. Terms with block index at least L are multiples of B^L and cannot affect lower digits. Thus truncated multiplication is exact modulo B^L, and the usual binary-exponentiation invariant yields a^b modulo B^L. Since B^L is a power of ten with at least k digits, the extracted digit is correct.
Watch out. Do not compute the full power or use floating-point logarithms. Carries must be propagated after convolution. A convolution entry is below 250*9999² plus carries, safely within signed 64-bit range.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Only the last k digits can affect the requested digit.
using namespace std;
const long long BASE=10000;
vector<long long>multiply(const vector<long long>&a,const vector<long long>&b){
int length=static_cast<int>(a.size());
vector<long long>product(length,0);
for(int i=0;i<length;++i){
if(a[i]==0){
continue;
}
for(int j=0;i+j<length;++j){
product[i+j]+=a[i]*b[j];
}
}
for(int i=0;i<length;++i){
if(i+1<length){
product[i+1]+=product[i]/BASE;
}
product[i]%=BASE;
}
return product;
}
int main(){
int tests;
cin>>tests;
while(tests--){
unsigned long long a,exponent;
int k;
cin>>a>>exponent>>k;
int blocks=(k+3)/4;
vector<long long>factor(blocks,0),result(blocks,0);
result[0]=1;
for(int i=0;i<blocks;++i){
factor[i]=a%BASE;
a/=BASE;
}
while(exponent>0){
if(exponent&1ULL){
result=multiply(result,factor);
}
exponent>>=1;
if(exponent>0){
factor=multiply(factor,factor);
}
}
long long digit=result[(k-1)/4];
for(int i=0;i<(k-1)%4;++i){
digit/=10;
}
cout<<digit%10<<'\n';
}
}