Returns single digit sum of a ^ n . We use modular exponentiation technique .
int powerDigitSum ( int a , int n ) { int res = 1 ; while ( n ) { if ( n % 2 == 1 ) { res = res * digSum ( a ) ; res = digSum ( res ) ; } a = digSum ( digSum ( a ) * digSum ( a ) ) ; n /= 2 ; } return res ; }