小w的a=b问题

题意

题目链接：https://ac.nowcoder.com/acm/contest/7023/A

分析

解法1-哈希

可以利用哈希映射，但是可以要选择合适的模数，一开始选择的是 (1e9+7)，不行，换成 (1e9+9) 才可以，或者 (2147483587)。

代码

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+10;
const int mod=1e9+9;//选择合适的模数1e9+7不行
ll fac[N];
void init()
{
    int maxn=1e5;
    fac[0]=1;
    for(int i=1;i<=maxn;i++)
        fac[i]=fac[i-1]*i%mod;
}
int main()
{
    int T,n,m,a;
    init();
    scanf("%d",&T);
    while(T--)
    {
        ll x=1,y=1;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a);
            x=x*fac[a]%mod;
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&a);
            y=y*fac[a]%mod;
        }
        if(x==y) printf("equal
");
        else printf("unequal
");
    }
    return 0;
}

解法2-质因子分解

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+10;
int prime[1010],cnt;
bool vis[1010];
int a[N],b[N],ma[N],mb[N];
void init()
{
    int maxn=1e3;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;prime[j]*i<=maxn;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int main()
{
    int T,n,m,x;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int maxn=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&x);
            a[x]++;
            maxn=max(maxn,x);
        }
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&x);
            b[x]++;
            maxn=max(maxn,x);
        }
        for(int i=maxn;i>=2;i--)//计最终的乘积中每个数出现的次数，从后向前
            a[i-1]+=a[i],b[i-1]+=b[i];
        for(int i=2;i<=maxn;i++)
        {
            int t=i;
            for(int j=1;prime[j]*prime[j]<=t&&j<=cnt;j++)//质因子分解
            {
                while(t%prime[j]==0)
                {
                    t/=prime[j];
                    ma[prime[j]]+=a[i];
                    mb[prime[j]]+=b[i];
                }
            }
            if(t>1) ma[t]+=a[i],mb[t]+=b[i];
        }
        bool f=1;
        for(int i=1;i<=1e5;i++)
        {
            if(ma[i]!=mb[i])
                f=0;
            ma[i]=0,mb[i]=0;
            a[i]=0,b[i]=0;
        }
        if(f) printf("equal
");
        else printf("unequal
");
    }
    return 0;
}