You're given $$$a$$$, $$$b$$$. the Lucky Number is the sum of first 3 digits and last 3 digits of $$$a^{b}$$$ $$$(a \leq 2 \times 10^{9})$$$ $$$(b \leq 10^{7})$$$,
It is guaranteed that $$$a^{b}$$$ contains at least $$$6$$$ digits.
Example if $$$a = 6$$$ and $$$b = 7$$$.
$$$a^{b} = 279936$$$ Lucky Number is $$$279 + 936 = 1215$$$
input : $$$a = 24, b = 13$$$ Output : $$$1700$$$
input : $$$a = 153456, b = 3$$$ Output : $$$1177$$$
The last three decimal digits can be found by computing the expontentiation $$$a^{b}$$$ $$$\mod 1000$$$.
The first three decimal digits require more mathematics. When $$$a = 6$$$ and $$$b = 7$$$, you can rewrite $$$a^{b} = 279936$$$ as $$$2.79936 \times 10^{5} = 10^{b \times \log10(a)}$$$. Suppose that $$$x = b \times \log10(a)$$$. In this example, the integr part of $$$x$$$ is equal to $$$5$$$. Suppose that the fractional part of $$$x$$$ is equal to $$$y$$$. Note that $$$y$$$ is equal to $$$\log10(2.79936)$$$. The last three digits are equal to the integer part of $$$100 \times 10^{y}$$$.
Look at the constraints. TLE.
Not really! The run-time for my C++ impelementation for the maximum values of $$$a$$$ and $$$b$$$ is 0 msec.
Thanks. I've learned a new thing.
For beginners like me, the formula:
(a ** b) % c = ((a % c) ** b) % c
With pleasure.
Thank you so much for this explaination
You can take the first 6 digits (or all if a has less than 6 digits) of a, let this x. Then the first 3 digits of x ** b matches the first 3 digits of a ** b.
Then you can take the last 3 digits (or all if a has less than 6 digits) of a, let this y. Then the last 3 digits of y ** b matches the last 3 digits of a ** b.