Product#28

Product (Editorial)

Written By : MathModel

Notice that $1 \leq a < b \leq 1 0^{4}$ 1 \le a < b \le 10^4 , thus the maximum integer that we'll get is $10000!$ , thus we should be using a language that supports big integers like Python.

From the constraints we also should pick "elegant" brute force , we can name the input integer as $n$ , we iterate from $a = 2$ a=2 to $a = 1 0^{4}$ a=10^4 and $b = a + 1$ b=a+1 to $b = 1 0^{4}$ b=10^4 , this is roughly $1 0^{8}$ 10^8 operations which is quite much , we can optimize this by dropping the cases that we want , which is exactly

i = a \prod b i > n

\prod_{i=a}^{b} i > n

Once this product is larger than $n$ we're just increasing and consuming time for no good reason , thus we just break once we've it ready.

Complexity roughly $O (1 0^{7})$ \mathcal{O}(10^7) which is a better optimization.

def solve():
    n=int(input())
    for a in range(2,10**4+1):
        cur=a
        for b in range(a+1,10**4+1):
            cur*=b
            if(cur==n):
                print(a,b)
                return
            if(cur>n):
                break
solve()

Python