### Cat.Noir's blog

By Cat.Noir, history, 2 months ago,

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$

• +2

 » 2 months ago, # | ← Rev. 10 →   +6 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}$.
•  » » 2 months ago, # ^ |   0 Look at the constraints. TLE.
•  » » » 2 months ago, # ^ |   0 Not really! The run-time for my C++ impelementation for the maximum values of $a$ and $b$ is 0 msec. 0 msec and 0 KB performance in C++20 #include using namespace std; int main() { double y; int a, b; cin >> a >> b; int64_t l, r = 1; for (int64_t x = a, y = b; y > 0; y >>= 1, x *= x, x %= 1000) if (y&1) r *= x, r %= 1000; modf(floor(100.0*pow(10,modf(b*log10(a),&y))),&y); l = floor(y); cout << l+r; } 
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   0 Thanks. I've learned a new thing.For beginners like me, the formula:(a ** b) % c = ((a % c) ** b) % c
•  » » » » » 2 months ago, # ^ |   0 With pleasure.
•  » » 2 months ago, # ^ |   0 Thank you so much for this explaination
 » 2 months ago, # | ← Rev. 4 →   -10 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.