题意：
给定n个最多9位小数的实数序列a，问有多少个有序数对<i,j>，满足a(i)*a(j)是整数
数据范围：n<=2e5，0<a(i)<1e4
解法：
将每个数乘上
1e9变成整数
,
那么我们要找的是乘积是
1e18的倍数的数对
.
分解出每个数质因子
2和
5的个数
,
那么可以计算出两个数相乘之后末尾有多少个
0,
如果
>=18则满足条件
然后每个数可以变为形如
(cnt2
,cnt5
)的数对
,
假设
(a
,b
)和
(c
,d
)相乘
,那么
0的个数为
min(a
+c
,b
+d
)
我们要找的就是
min(a
+c
,b
+d
)>=18的数对个数
因为n最大
2e5,枚举数对肯定不行
.
考虑到每个数对中
2的个数最多
log(1e4*1e9)<45,
那么直接开二维桶g
[x
][y
]表示数对为
(x
,y
)的数量
,
枚举乘积的结果数对即可
,复杂度
O(70*70*45*45)<1e7
code：
#include<bits/stdc++.h>
using namespace std
;
#define int long long
#define PI pair<int,int>
const int maxm
=2e5+5;
int num
[45][45];
int a
[maxm
];
int n
;
signed main(){
ios
::sync_with_stdio(0);
cin
>>n
;
for(int i
=1;i
<=n
;i
++){
string s
;cin
>>s
;
int num
=0;
int cnt
=-1;
for(auto x
:s
){
if(isdigit(x
)){
num
=num
*10+x
-'0';
if(cnt
>0)cnt
--;
}else{
cnt
=9;
}
}
if(cnt
==-1)cnt
=9;
while(cnt
-->0)num
=num
*10;
a
[i
]=num
;
}
for(int i
=1;i
<=n
;i
++){
int c2
=0,c5
=0;
while(a
[i
]%2==0){
c2
++;
a
[i
]/=2;
}
while(a
[i
]%5==0){
c5
++;
a
[i
]/=5;
}
num
[c2
][c5
]++;
}
int ans
=0;
for(int i
=18;i
<=90;i
++){
for(int j
=18;j
<=90;j
++){
for(int x
=0;x
<45&&x
<=i
;x
++){
for(int y
=0;y
<45&&y
<=j
;y
++){
int xx
=i
-x
,yy
=j
-y
;
if(xx
<0||xx
>=45||yy
<0||yy
>=45)continue;
if(xx
==x
&&yy
==y
){
ans
+=num
[x
][y
]*(num
[x
][y
]-1);
}else{
ans
+=num
[x
][y
]*num
[xx
][yy
];
}
}
}
}
}
ans
/=2;
cout
<<ans
<<endl
;
return 0;
}
