解説

この問題を作ってからその存在を知りましたが、 ヤコビの二平方和定理 を用いれば良いです。具体的には ルジャンドルの定理 を用いて $\prod_{i=1}^{N} A_i!$ を素因数分解した後、 定理を適用すれば解くことができます。 $max(A_i) = M$ とすると計算量は $O(NM)$ となり、これは十分に高速です。