Cat.Noir's blog

By Cat.Noir, history, 2 months ago, In English

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$$$

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
2 months ago, # |
Rev. 10   Vote: I like it +6 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at the constraints. TLE.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you so much for this explaination

»
2 months ago, # |
Rev. 4   Vote: I like it -10 Vote: I do not like it

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.