题解：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 已经绰绰有余。

::::success[code]

#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;
}

::::