小w的a=b问题(欧拉筛或者hash做法)

78 阅读 0 评论 52 点赞

我是靠谱客的博主缓慢导师，最近开发中收集的这篇文章主要介绍小w的a=b问题(欧拉筛或者hash做法)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接·

题意：不解释了。。。

做法一：先将每个阶乘分解，用一个sum数组保存每个乘数出现的次数（先统计每个阶乘出现的次数，再从后面往前使用前缀和）。对于每个合数将其分解质因数，最后只要比较sum数组每个数出现的个数是否相等就能判断答案了。

分解质因数这里用到了欧拉筛，欧拉筛每次会用两个数将一个合数筛掉，一个是这个合数的最小质数，另一个数不确定。
这时候我们开一个结构体保存这两个数，这两个数就是这个合数分解出来的数。
因为另一个数不知道他到底是质数还是合数，所以必须从后往前遍历（从前往后的话就会造成一些合数又分解出了新的合数，会导致分解不干净）。
遍历到的这个数如果是合数，那么就将这个合数分解。
具体操作就是，sum这个合数置为0，而他分解的两个数的sum加上这个数的值。
这样扫一遍就能把每个合数分解干净了，这个时候sum数组就只保存了质数的个数。

#include<bits/stdc++.h>
using namespace std;
#define  reg register
const int maxn = 1e5+100;
int prime[maxn];
int visit[maxn];
struct node{
	int x,y;
}pre[maxn];//保存每个合数能分解的两个数 
inline void Prime(){
    memset(visit,0,sizeof(visit));
    memset(prime,0,sizeof(prime));
    for (reg int i = 2;i <= 100010; ++i) {
        if (!visit[i]) {
            prime[++prime[0]] = i; 
        }
        for (int j = 1; j <=prime[0] && i*prime[j] <= maxn; j++) {
            visit[i*prime[j]] = 1;
            pre[i*prime[j]].x=i;//另一个数可能是合数，可能是质数 
            pre[i*prime[j]].y=prime[j];//这个合数的最小质数 
            if (i % prime[j] == 0) {
                break;
            }
        }
    }
}
typedef long long ll;
ll sum1[maxn],sum2[maxn];
int main()
{
	Prime();
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m,x,mx=0;
		scanf("%d%d",&n,&m);
		for(reg int i=1;i<=n;++i){
			scanf("%d",&x);
			mx=max(mx,x);//保存阶乘最大值 
			sum1[x]++;//统计每个阶乘出现的次数 
		}
		for(reg int i=1;i<=m;++i){
			scanf("%d",&x);
			mx=max(mx,x);
			sum2[x]++;
		} 
		for(reg int i=mx;i>=1;--i){//将阶乘展开 
			sum1[i]+=sum1[i+1];
			sum2[i]+=sum2[i+1];
		} 
		for(reg int i=mx;i>=1;--i){
			if(visit[i]){//如果是合数 
				sum1[pre[i].x]+=sum1[i];//进行分解 
				sum1[pre[i].y]+=sum1[i];
				sum1[i]=0;
				sum2[pre[i].x]+=sum2[i];
				sum2[pre[i].y]+=sum2[i];
				sum2[i]=0;
			}
		} 
		int flag=1;
		for(reg int i=2;i<=mx&&flag;++i){
			if(sum1[i]!=sum2[i]) flag=0;//比较每个数出现的次数是否相等 
		}
		for(int i=1;i<=mx;i++) sum1[i]=sum2[i]=0;
		puts(flag?"equal":"unequal");
	}
 }

做法二：用hash将每个阶乘预处理出来，然后相乘再比较大小。一脸懵逼，感觉这种做法非常玄学，最重要的是要找好质数，如果质数没找好就会wa，质数找好了就能AC，能不能过全看命呀orz。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
ll mod[6] = {0, 1000000000+7, 1000000+7, 100000000+7, 20000000+7, 10000000+7};
ll pre[N][6], a[N], b[N];
void init(){
	for(int i = 1; i <= 5; ++i){
		pre[0][i] = 1;
		for(int j = 1; j <= N - 7; ++j)
			pre[j][i] = pre[j - 1][i] * j % mod[i];
	}
}
int main()
{
	init();
	int T;
	scanf("%d", &T);
	while(T--){
		int n, m;
		scanf("%d%d", &n, &m);
		for(int i = 1; i <= n; ++i)
			scanf("%d", &a[i]);
		for(int i = 1; i <= m; ++i)
			scanf("%d", &b[i]);
		int flag = 1;
		for(int i = 1; i <= 5 && flag; ++i){
			ll tmp1 = 1, tmp2 = 1;
			for(int j = 1; j <= n; ++j)
				tmp1 = pre[a[j]][i] * tmp1 % mod[i];
			for(int j = 1; j <= m; ++j)
				tmp2 = pre[b[j]][i] * tmp2 % mod[i];
			if(tmp1 != tmp2)
				flag = 0; 
		}
		puts(flag ? "equal" : "unequal");
	}
}