Given an array of N integers where $2 ≤ N ≤ 2×10^5$ and each element in array is less than $10^{16}$. Now I am given a variable $X$ that can also go up to $10^{16}$.
We need to find if $X \mid A_0^{A_1^{A_2^{\unicode{x22f0}^{A_N}}}}$.
How to solve this problem?
Obviously computing the power here is not feasible.
On
Let $B_0 = A_0$ and compute $B_{n+1} = B_n / gcd (B_n, X)$ until you reach two identical values for $B_n$ (which will happen for $n \le \log (10^{16})/\log 2 \le 54$)
Say $B_n = B_{n+1}$.
If $B_n = 1$, then $X$ divides $A_0^n$ (and clearly, $A_1^{A_2^\ldots}$ is greater than $n$ most of the time).
If $B_n \neq 1$, then $X$ has prime factors not occuring in $A_0$ so $X$ doesn't divide any $A_0^p$ for any $p$.
1) Calculate $g=gcd(A_o,X)$.
2) Factorize $g$.
3) Select smallest among $A_0$ and $X$, let it be $X$.
4) For each distinct prime factor $p$ of $g$
4.1) Find arity $r$ (power of that prime number $p$ in $X$) of $p$ with respect to $X$.
4.2) Divide $X$ with $p^r$ for each such $p$ and store the result in $X$.
5) Now our $X$ is free from all common prime factors with $A_0$, So now if our resulted $X\ne 1$ then it contains a prime number that is not in $A_0$, so then $X \nmid A_0$.
Note : Finding arity of a prime number can be achieved in lesser time (order of arity ).
Example : $X=3^3*5^9*7^2$ and $A_0 = 3^2*5^{11}*11^3$
1)$gcd=g=3^2*5^9$
2) 3,5 are prime factors of $g$.
3) select either $X$or $A_0$ .(no restriction on minimum of both).
4) if you select $X$ then $X$ becomes $7^2$ else if u select $A_0$, it becomes $11^3$ . (we are dividing with prime factors of $g$ ).
5) Now if you select $X$,$X\ne 1$ , so $X$ has prime factor(7) that is not in $A_0$. similarly for $A_0$.