Another Problem about Beautiful Pairs

The condition is

$a_i\cdot a_j=j-i.$

Because $a_i,a_j>0$, the right side must be positive, so automatically $i<j$. That is useful: no weird symmetric counting, no zero-distance nonsense.

A first rewrite is:

$j=i+a_i\cdot a_j.$

So if we fix $i$ and guess $a_j=x$, then the position $j$ is forced to be exactly $i+a_i x$. The dumb version guesses every possible $x$, but $a_j$ can be up to $10^9$, so that is not directly fine.

The escape hatch is the usual square-root split. Pick a threshold $B$ around $\sqrt n$; using $B=500$ is enough because $n\le 2\cdot 10^5$.

We separate array values into:

• small: $a_i<B$
• large: $a_i\ge B$

Now count pairs without double-counting.

For every index $i$:

1. If $a_i<B$, enumerate only small possible right values $x=1,2,\dots,B-1$. The only candidate right index is $j=i+a_i x.$ If $j<n$ and $a_j=x$, then $(i,j)$ is beautiful.

   This counts exactly the pairs whose left value is small and whose right value is small.

2. If $a_i\ge B$, scan positions at distances that are multiples of $a_i$:

   • to the right: $j=i+a_i x$; if $a_j=x$, then $(i,j)$ is beautiful;
   • to the left: $j=i-a_i x$; if $a_j=x$, then $(j,i)$ is beautiful.

   This counts every pair where the current large value participates. Yes, both directions are needed: the large value might be on the left or on the right.

Why does this not double-count?

• If both values are small, the pair is counted only when processing the left index in the small case.
• If the left value is large, it is counted when processing that large left index and scanning right.
• If the right value is large and the left value is small, it is counted when processing that large right index and scanning left.
• If both values are large, then both scans might look suspicious, but actually such a pair cannot exist when $B^2>n-1$, because $a_i a_j\ge B^2>j-i.$ With $B=500$, $B^2=250000>2\cdot 10^5$, so large-large pairs are impossible. The math slams that door shut.

Complexity:

• Small values do at most $B$ checks per index: $O(nB)$.
• Large values scan at most $O(n/a_i)\le O(n/B)$ positions per direction, so across all indices this is bounded by $O(n^2/B)$.

With $B\approx \sqrt n$, this is about $O(n\sqrt n)$, easily fine for $\sum n\le 2\cdot 10^5$.

Memory usage is $O(n)$. Edge cases like huge $a_i$ are harmless: their multiple scans stop immediately, because the first jump already leaves the array.