题解：AT_agc047_a [AGC047A] Integer Product
RioFutaba
·
·
题解
题意
给定 n 个实数 A_1 到 A_n，求有多少对 i,j（i<j）使得 A_i \times A_j 是整数。
## 解法
显然，$A_i \times 10^9$ 是一个整数。如果 $A_i \times A_j$ 是整数，那么 $(A_i \times 10^9) \times (A_j \times 10^9)$ 后面得有 $18$ 个 $0$，也就是它是 $10^8$ 的倍数。
如果一个数是 $10^8$ 的倍数，那么它质因子 $2$ 的个数和 $5$ 的个数都 $\geq 18$。
先把每个 $A_i$ 都乘上 $10^9$，计算出它质因子 $2$ 和 $5$ 的个数。再暴力判断之前有多少个数和它乘在一起符号要求。
```cpp
#include <bits/stdc++.h>
using namespace std;
#define db long double
#define ll long long
const int maxn=2e5+5;
int n;
ll ans,cnt[50][20];//cnt[i][j] 表示质因子2的个数为i，5的个数为j的数的个数
db a[maxn];
int main(){
cin >> n;
for(int i=1;i<=n;i++){
scanf("%Le",&a[i]);
int c2=0,c5=0;
ll x=round(a[i]*1e9);//round一下，不然精度会爆炸
while(!(x%2)) x/=2,c2++;
while(!(x%5)) x/=5,c5++;//计算
for(int j=18-c2;j<50;j++)
for(int k=18-c5;k<20;k++)
ans+=cnt[j][k];
cnt[c2][c5]++;
}
printf("%lld\n",ans);
return 0;
}
```