この問題はフェルマーの小定理の応用を問います。

$(x,y)$ の範囲を全探索しようとしても、言語によってはかなり無謀な計画になってしまいます。そもそも $(i,j)$ を全探索するわけですから、$O(N^2)$ となって間に合いません。ではどうすればよいのでしょうか？

結論から言うと、以下のいずれかを満たすときに限り必ず $(x,y)$ の組は存在します。

• ① $A_i,A_j$ がともに $K$ と互いに素である (すなわち $gcd(A_i,K)=1$ かつ $gcd(A_j,K)=1$ が成り立つ)
• ② $A_i,A_j$ がともに $K$ と互いに素でない (すなわち $gcd(A_i,K)\neq 1$ かつ $gcd(A_j,K)\neq 1$ が成り立つ)

上において、①はフェルマーの小定理を用いて証明できます。以下がその証明です。

$proof(①)$

背理法から示す。
正整数 $a,b$、素数 $K$ とする。$a,b$ ともに $K$ と互いに素であるとき、条件を満たす $(x,y)$ の組が存在しないと仮定する。
(すなわち $a^x-b^y\equiv 0\ (mod\ K)$ が成り立つ $(x,y)$ が存在しないと仮定)

フェルマーの小定理より、

$a^{K-1}\equiv 1\ (mod\ K)$ 同様にして $b^{K-1}\equiv 1\ (mod\ K)$

よって合同式の性質より、

$a^{K-1}-b^{K-1}\equiv 0\ (mod\ K)$ ( $2$ 式の右辺、左辺同士を引いた)

となり、これは $(x,y)=(K-1,K-1)$ のときに条件を満たすため、仮定に矛盾が生じる。

したがって①は成り立つ。

②に対して、これは明らかに条件を満たす $(x,y)$ の組は存在しますが、一応証明を以下に記します。

$proof(②)$

ここでは背理法ではなく性質を使って示す。
①の時と同じく正整数 $a,b$ (便宜上 $a\ge b$ とする)、素数 $K$ とする。$a,b$ がともに $K$ と互いに素でない正整数であるとする。

フェルマーの小定理より、

$a^K\equiv a\ (mod\ K)$ 同様にして $b^K\equiv b\ (mod\ K)$

合同式の性質より、

$a^K-b^K\equiv a-b\ (mod\ K)$

ここで $K$ は素数であることから、$K$ の素因数は $K$ のみであり、他に $K$ の素因数はないことは自明である。
つまり $a,b$ が $K$ と互いに素でないならば $\frac{a}{K},\frac{b}{K}$ はともに整数となることがわかる (ここで $a\ge K,b\ge K$ であることに注意※$_1$)。
よって $a\equiv 0\ (mod\ K)$ また $b\equiv 0\ (mod\ K)$ である。

したがって $a-b\equiv 0\ (mod\ K)$ が成り立つことから、$a^K-b^K\equiv a-b\equiv 0\ (mod\ K)$ より、②も成り立つ。

よって上の条件①、②毎のグループに要素を採用していって、そのグループ内から $2$ 要素を選べば良いです。
この時選び方は①を満たすグループ内に属する要素の個数 $n$ として、$_nC_2=\frac{n(n-1)}{2}$ 通りあるので、
答えは $_nC_2+_{N-n}C_2=\frac{n(n-1)}{2}+\frac{(N-n)(N-n-1)}{2}$ ※$_2$となります。

以上から、$A_i$ と$K$ が互いに素かどうか判定するのにユークリッドの互除法などを用いて $O(\log_{}A_i)$ かかるので、全体で $O(N\max (\log_{}A_i))$ で実装できます。以下は解答例(C++,Python)です。

(解答例では上の情報から $a\not\equiv 0\ (mod\ K)$ が $a$ と $K$ は互いに素であることの必要十分条件ですから、単に $A_i$ を $K$ で割ったあまりが $0$ でないかで判定しています。ゆえに $O(N)$ でも実装できます)

※$_1$ $a,b$ は $K$ と互いに素でないことから、何らかの正整数 $x$ を掛け合わせてできる整数であるため、$a$ を $ax$ に、$b$ を $bx$ としてもこの値は明らかに $a\ge K,b\ge K$ となります。

※$_2$ ②を満たすような選び方は、$N$ 個全体の要素の個数から $n$ 個だけ①で既に採用されているため $_{N-n}C_2$ 通りです。いずれの条件①②に対しても独立なので、この通り数の総和が答えとなります。