What I learned today?

knowledge

#1

When we multiply two numbers like (10^18)*(10^18) then it will exceed the long long int max value(i.e 10^18). In such case we use __int128.

128-bit Integers:

As an extension the integer scalar type __int128 is supported for targets which have an integer mode wide enough to hold 128 bits. Simply write__int128 for a signed 128-bit integer, or unsigned __int128 for an unsigned 128-bit integer.

Can be applied in the given question–>https://www.codechef.com/DRI22019/problems/VNFAR


#2

Suppose you didn’t know about 128 bit integer in C++ or as in case java you don’t know about BigInteger class or you are fully aware of BigInteger class time complexity of multiplication which by the way is not constant, its linear, then how would you do the question?

The solution is the fact that multiplication is repeated addition, same way the power is repeated multiplication. But we have to reduce the complexity of add function from \mathcal{O}(n) to \mathcal{O}(logn) the same we reduce the complexity of power function.