【AGC047A】Integer Product

思路和标程类似，但是没用 map。

首先 \(n^2\) 暴力显然不过我不敢保证你会不会被卡掉精度

看到数据范围果断想低于 \(n^2\) 的做法。

小数点后不超过 \(9\) 位，这能给我们什么启示？

将每个 \(A_i\) 乘上 \(10^9\)，记为 \(B_i\)。容易发现若 \(A_i\times A_j\) 为整数，\(10^{18}\mid B_i\times B_j\)。

而小学数学告诉我们，若一个数有 \(m\) 个因子 \(2\)，\(n\) 个因子 \(5\)，它末尾零的个数为 \(\min(m,n)\)。

标程使用 map，但是实际上这个数字并不大，直接用桶记录。

#include <map>
#include <stdio.h>
long long f[50][50];
int n,i,j,p,q,cnt1,cnt2;
long long mid,res;
long double x;
int main()
{
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		cnt1=cnt2=0;
		scanf("%Lf",&x);
		mid=(long long)(x*1000000000+0.5);
		while(mid%2==0)
		{
			++cnt1;
			mid/=2;
		}
		while(mid%5==0)
		{
			++cnt2;
			mid/=5;
		}
		++f[cnt1][cnt2];
	}
	for(i=18;i<=90;++i)
	{
		for(j=18;j<=90;++j)
		{
			for(p=0;p<45&&p<=i;++p)
			{
				for(q=0;q<45&&q<=j;++q)
				{
					if(i-p>44||j-q>44)
						continue;
					if(i!=2*p||j!=2*q)
						res+=f[p][q]*f[i-p][j-q];
					else
						res+=f[p][q]*(f[p][q]-1);
				}
			}
		}
	}
	printf("%lld",res>>1);
	return 0;
}

写挂时参考了网上题解和官方题解。

表示膜拜。