题解：AT_agc047_a [AGC047A] Integer Product

这题很明显可以将所有的

A

同时乘上

10^9

，问题就变成了正整数

A

数组，求

A_i\times A_j

结果为

10^{18}

的倍数的下标对个数。我们都知道两数相乘，结尾的

0

的个数为两数

2

的因子数量之和与

5

的因子数量之和的较小值。

所以我们把每个

A

乘

10^9

后的

2

因子和

5

因子分解为出来，分别记其数量为

a

和

b

。则变成了要求

\min(a_i+a_j,b_i+b_j) \ge 18

的下标对个数。

我们可以写一个二维数组

c_{i,j}

，先记

c_{i,j}

是

a

为

i

并且

b

为

j

的数的个数。然后对

c

进行二位后缀和。我们就可以发现含有

i

的数对的个数应该是

c_{\max(0,18-a_i),\max(0,18-b_i)}

，所以我们累加这个值。
但是可能会出现

18-a_i \le a_i

并且

18-b_i \le b_i

的情况，此时

c_{\max(0,18-a_i),\max(0,18-b_i)}

记录的结果里包括了

i

产生的贡献，所以要减

1

来减去

i=j

的不合法情况。
最后的结果还会出现

i>j

的情况，只需除

2

即可。

可以发现

a

和

b

的最大值都很小，

c

数组开

100

已经绰绰有余。

code

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int maxn=2e5+5,mod=1e9+7;
int a2[maxn],a5[maxn],c[105][105],n,s=0;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		double aa;
		int a;
		cin>>aa;
		a=(int)((aa+0.0000000005)*(1000000000.0));//这里加 0.0000000005 是为了防止 double 的误差 
		a2[i]=0,a5[i]=0;
		while(a%2==0)a2[i]++,a/=2;
		while(a%5==0)a5[i]++,a/=5;
		c[a2[i]][a5[i]]++;
	}
	for(int i=100;i>=0;i--)for(int j=100;j>=0;j--)c[i][j]+=c[i+1][j]+c[i][j+1]-c[i+1][j+1];
	int k=0;
	for(int i=1;i<=n;i++)
	{
		int x=18-a2[i],y=18-a5[i];
		if(x<0)x=0;
		if(y<0)y=0;
		s+=c[x][y];
		if(x<=a2[i] && y<=a5[i])s--;
	}
	cout<<s/2;
	return 0;
}

题解：AT_agc047_a [AGC047A] Integer Product

文章操作

相关推荐

评论

题解：AT_agc047_a [AGC047A] Integer Product