Find the last digit of given series | C ++ program to calculate to find last digit of above expression ; Iterative Function to calculate ( x ^ y ) % p in O ( log y ) ; x = x % p ; Update x if it is more than or equal to p ; If y is odd , multiply x with result ; y must be even now y = y >> 1L L ; y = y / 2 ; Returns modulo inverse of a with respect to m using extended Euclid Algorithm ; q is quotient ; m is remainder now , process same as Euclid 's algo ; Make x1 positive ; Function to calculate the above expression ; Initialize the result ; Compute first part of expression ; Compute second part of expression i . e . , ( ( 4 ^ ( n + 1 ) - 1 ) / 3 ) mod 10 Since division of 3 in modulo can ' t ▁ ▁ be ▁ performed ▁ directly ▁ therefore ▁ we ▁ ▁ need ▁ to ▁ find ▁ it ' s modulo Inverse ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; long long powermod ( long long x , long long y , long long p ) { while ( y > 0 ) { if ( y & 1LL ) res = ( res * x ) % p ; x = ( x * x ) % p ; } return res ; } long long modInverse ( long long a , long long m ) { long long m0 = m , t , q ; long long x0 = 0 , x1 = 1 ; if ( m == 1 ) return 0 ; while ( a > 1 ) { q = a / m ; t = m ; m = a % m , a = t ; t = x0 ; x0 = x1 - q * x0 ; x1 = t ; } if ( x1 < 0 ) x1 += m0 ; return x1 ; } long long evaluteExpression ( long long & n ) { long long firstsum = 0 , mod = 10 ; for ( long long i = 2 , j = 0 ; ( 1LL << j ) <= n ; i *= i , ++ j ) firstsum = ( firstsum + i ) % mod ; long long secondsum = ( powermod ( 4LL , n + 1 , mod ) - 1 ) * modInverse ( 3LL , mod ) ; return ( firstsum * secondsum ) % mod ; } int main ( ) { long long n = 3 ; cout << evaluteExpression ( n ) << endl ; n = 10 ; cout << evaluteExpression ( n ) ; return 0 ; }