Here is my solution though, first bruteforce the first number, then find its prime factorization after that it is only a matter of calculating how many numbers in interval $$$[MIN;MAX]$$$ does not share a prime factor with the current candidate for $$$a_1$$$. It is easier to calculate the inverse problem ie. how many share at least one. This can be done with inclusion-exclusion principle, with that calculate the answer for numbers upto $$$MAX$$$ and upto $$$MIN-1$$$, their difference gives the answer for the interval. So we have the number of non relative primes to $$$a_1$$$ in the interval and given that a number can either be non relative prime to any other or relative prime, we also have the number of relative primes to $$$a_1$$$ in range $$$[MIN;MAX]$$$, $$$k$$$. For this fixed first number the answer is $$$k^{n-1}$$$. Complexity is bounded by the maximum number of distinct prime factors, in the given range it is six since $$$2*3*5*7*11*13<10^5$$$ but $$$2*3*5*7*11*13*17>10^5$$$, thus a definite worst-case complexity is $$$\mathcal{O}(n * 2^6)$$$.