Блог пользователя fried-chicken

Автор fried-chicken, история, 3 года назад, По-английски

This is a problem from 2021 ICPC Shannxi invitational and confuse me a lot. Since this contest have neither place to up-solving nor tutorial, I'm here to ask for idea and help.

The problem is like:

Given a number X, we call another number N is a lucky number to X if:

  1. N is larger than 1e8;
  2. N is smaller than 1e13;
  3. (N!) begins with X.

For example, if we ignore the first constraint, N=10 is a lucky number to X=3628 since (10!)=3628800.

Now, given T testcases, each testcases gives you a X, output any N where N is a lucky number to X.

T is smaller than 200 and X is smaller than 1e5.

Sample input

2

494

997

Sample output

1000001586369

1000001980150

UPD: Thanks everybody for helping, I think using stirling's and brute force is the right one.

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

Disregarding precision issues, using the Stirling series approximation to the second term, we have

$$$ N! \approx \sqrt{2 \pi N} \left(\frac{N}{e}\right)^N \cdot \left(1 + \frac{1}{12N}\right) $$$

with a relative error of $$$O\left(\frac{1}{N^2}\right)$$$, which should suffice to find the first $$$10^5$$$ digits (if you take logarithms).

Implementing this might be pretty painful though (if precision issues persist, Newton Raphson to do exponentiation for bigints should do the trick).

Edit: I misread the problem, the solution here might not be helpful in solving the original problem.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe brute force?

If the distribution is random, it may be possible to store only the highest few post-violence.

And, Preprocessing $$$10^8!$$$.

»
3 года назад, # |
Rev. 12   Проголосовать: нравится 0 Проголосовать: не нравится

Check if the following Stirling's approximation solution is accurate enough to work or not.

C++

Since $$$1 \leq X < 10^5$$$, it should be sufficient to check if the $$$k$$$-digit prefix of $$$N!$$$, where $$$1 \leq k \leq 5$$$, is equal to $$$X$$$.

This program reported the following prompt to cerr.

prompt

2,184,933 preprocessing iterations of Stirling's approximation computation were sufficient to find the answers to all possible values of $$$X$$$.

In Codeforces C++20 custom test, the preprocessing part consumed 624 ms execution time.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I made a brute force, and it seems to work.

I just copied the value of (10^8)! from Wolfram Alpha. In the brute force I try every factorial from 1e8+1 onwards until I find the right prefix, (it only takes around 10^6 tries in the worst case to find the right prefix) . To make the numbers fit in a long double, I divide by 10 when needed. Then it's just hoping there are no precision errors :)

Edit: I checked what the largest needed value of n was. In my program it is 102184933.

c++
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by fried-chicken (previous revision, new revision, compare).

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

I have just checked out of curiosity the maximum absolute difference between approximating $$$N!$$$ as $$$f\times 10^g$$$, where $$$1 \leq f < 10$$$ and $$$g$$$ is non-negative integer using Stirling's approximation, and using the power function of logarithmic summation.

$$$ N! = 10^{\sum\limits_{x=1}^{x=N} log_{10}(x)}$$$

I found that the maximum absolute difference between the two approximations is 0.0000031938, which is less than $$$10^{-5}$$$. The execution-time for the logarithmic summation in Codeforces custom test is about 3500 ms. It seems reasonable to claim that Stirling's approximation is fast and accurate enough to provide the correct answer for at most 5-digit prefix of $$$N!$$$ of the given constraints $$$1 \leq X < 10^5$$$ and $$$N > 10^8$$$.