由于小数点后不超过 \(9\) 位，所以在输入时给每个 \(A_i\) 乘上 \(10^9\) 并记为 \(B_i\)，这样问题就转换成了对于每个 \(a_i\)，有多少个 \(j\) 满足 \(j<i\) 且 \(10^{18}\mid B_j \times B_i\)。记 \(B_i\) 分解质因数后有 \(a_i\) 个因子 \(2\)，有 \(b_i\) 个因子 \(5\)，显然上述要求就是 \(a_j+a_i\ge 18\) 且 \(b_j+b_i \ge 18\)。所以对于 \(B_i\) 可能的 \(j\) 必须满足 \(a_j\ge \max(0,18-a_i)\) 且 \(b_j\ge \max(0,18-b_i)\)。使用二维树状数组维护和计算即可。
#include<bits/stdc++.h>
#define int long long
#define M 65
#define N 200005
using namespace std;
const int inf=1e18,sj=1e9,m=M-5;
int n,a[N],tree[M][M],ans;
int lb(int x){return x&(-x);
}
void add(int x,int y){for(int i=x;i<=m;i+=lb(i)){for(int j=y;j<=m;j+=lb(j)){tree[i][j]++;}}
}
int que(int x,int y){int tans=0;for(int i=m;i;i-=lb(i)){for(int j=m;j;j-=lb(j)){tans+=tree[i][j];}}for(int i=x-1;i;i-=lb(i)){for(int j=m;j;j-=lb(j)){tans-=tree[i][j];}}for(int i=m;i;i-=lb(i)){for(int j=y-1;j;j-=lb(j)){tans-=tree[i][j];}}for(int i=x-1;i;i-=lb(i)){for(int j=y-1;j;j-=lb(j)){tans+=tree[i][j];}}return tans;
}
signed main(){
// freopen("integer.in","r",stdin);
// freopen("integer.out","w",stdout);scanf("%lld",&n);for(int i=1;i<=n;i++){double tx;scanf("%lf",&tx);for(int j=1;j<=9;j++)tx*=10;int x=tx+0.5;int ta=0,tb=0;//cout<<x<<"\n";while(x%2==0)ta++,x/=2;while(x%5==0)tb++,x/=5;//cout<<ta<<' '<<tb<<"\n";int qa=max(0ll,18-ta),qb=max(0ll,18-tb);ans+=que(qa+1,qb+1);add(ta+1,tb+1);}printf("%lld\n",ans);return 0;
}