Original proposer: admin

First of all, let us only take into account the following conditions:

• \(1 \le i,j,k \le N\)
• \(A_i : A_j : A_k = 7:5:3\)

Since the elements of \(A\) are positive integers, the second conditions can be rephrased as follows:

• One can represent as \(A_i=7t,A_j=5t\), and \(A_k=3t\) for some positive integer \(t\).

We also see that \(A_i,A_j\), and \(A_k\) are pairwise distinct.

By this fact, we obtain the following solution:

• For each element \(A_l\) of \(A\), we have the following facts:
  • If \(A_l\) is a multiple of \(7\), then the element is eligible for \(i=l\), with \(t=A_l/7\).
  • If \(A_l\) is a multiple of \(5\), then the element is eligible for \(j=l\), with \(t=A_l/5\).
  • If \(A_l\) is a multiple of \(3\), then the element is eligible for \(k=l\), with \(t=A_l/3\).
  • Since \(A_i\), \(A_j\), and \(A_k\) are pairwise distinct for a valid tuple \((i,j,k)\), one can count the number of tuples for each fixed \(t\) by multiplying the number of candidates for \(i\), for \(j\), and for \(k\).

Thus, we have solved the problem, with the following condition excluded:

• \(\min(i,j,k)=j\) and \(\max(i,j,k)=j\)

How can we impose this constraint?
For simplicity, let us count the number of tuples as above, and subtract the number of tuples such that:

• When \(i\), \(j\), and \(k\) are sorted in ascending order, \(j\) comes the second.

This case can also be counted by processing for each \(t\) as follows:

• For each candidate of \(j\), the number of cases where \(i<j<k\) can be found as the product of the number of indices \(i\) smaller than that \(j\), and indices \(k\) larger than \(j\).
• For each candidate of \(j\), the number of cases where \(k<j<i\) can be found as the product of the number of indices \(k\) smaller than that \(j\), and indices \(i\) larger than \(j\).

This can be implemented in the manner of event sorting.

Note that the answer may be come so large that it exceeds the range of a \(32\)-bit integer type. Since the answer can be loosely upper-bounded by \((3 \times 10^5)^3\), we can assert that it fits in a \(64\)-bit integer type.

This solution runs in \(O(N \log N)\) time.

Sample code (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;

ll solve(vector<ll> &v7,vector<ll> &v5,vector<ll> &v3){
  ll res=ssize(v7);
  res*=ssize(v5);
  res*=ssize(v3);
  if(res==0){return 0;}

  vector<pl> vp;
  for(auto &nx : v7){vp.push_back({nx,7});}
  for(auto &nx : v5){vp.push_back({nx,5});}
  for(auto &nx : v3){vp.push_back({nx,3});}
  sort(vp.begin(),vp.end());
  ll p7=0,s7=v7.size();
  ll p3=0,s3=v3.size();
  for(auto &nx : vp){
    if(nx.second==7){
      p7++; s7--;
    }
    else if(nx.second==5){
      res-=p7*s3;
      res-=p3*s7;
    }
    else if(nx.second==3){
      p3++; s3--;
    }
  }
  return res;
}

int main(){
  ll n;
  cin >> n;
  map<pl,vector<ll>> mp;
  set<ll> tst;
  for(ll i=0;i<n;i++){
    ll a;
    cin >> a;
    if(a%7==0){
      mp[{a/7,7}].push_back(i);
      tst.insert(a/7);
    }
    if(a%5==0){mp[{a/5,5}].push_back(i);}
    if(a%3==0){mp[{a/3,3}].push_back(i);}
  }
  ll res=0;
  for(auto &nx : tst){
    res+=solve(mp[{nx,7}],mp[{nx,5}],mp[{nx,3}]);
  }
  cout << res << "\n";
  return 0;
}