解説

以下のような方針は，いずれも $N\le 10^6$ という制約の下では制限時間に間に合わないと思います．

• $A_1=X$ として，$i=2,3,\dots,N$ の順に $A_i$ を求める．
  $A_i=i$ と初期化し，各 $j=1,2,\dots,i-1$ に対して $j$ が $i$ の約数ならば $A_i$ に $A_j$ をかける．計算量は $O(N^2)$．
• 上記の方針において，$j$ が $i$ の約数であるような $j$ を求める操作を，素因数分解を用いて高速化する．計算量は $O(N\sqrt{N})$．

上記の方針では，「各 $i$ に対して，$i$ より小さい $j$ について， $A_i$ に $A_j$ をかける」という操作を行っていました．
操作の見方を変えて，「各 $j$ に対して，$j$ より大きい $i$ について， $A_i$ に $A_j$ をかける」という操作を行う以下のような方針を考えてみます．

• $j=1,2,\dots,N$ の順に $A_j$ を求める．$A_1=X$，$A_j=j$ と初期化しておく．
  各 $j$ について $i=2j,3j,\dots$ に対して $A_i$ に $A_j$ をかける．

この方針の計算量を評価します．ある $j$ に対して $N$ 以下の正の整数のうち $j$ の倍数であるものの個数は $\lfloor\frac{N}{j}\rfloor$ です．
よって，$j=1,2,\dots,N$ に対して考える場合の計算量は $O(N(1+\frac{1}{2}+\cdots+\frac{1}{N}))$ となりますが，これは $O(N\log N)$ と等しいです（調和級数）．
一見すると操作の見方を変えただけですが，計算量が改善されたことにより問題を解くことができます．
これは，約数を探索する場合には素因数分解の際に約数でない数も探索する必要があるため，無駄な計算時間がかかってしまうことに起因します．