7-6 莫比乌斯最大值isUsefulAlgorithm（2023郑州轻工业大学校赛

题意：
a数组有n个数，b数组有n个数
从a，b两个数组中任选两个数a[i],b[j]，算出值a[i] * b[j] * gcd(a[i],b[j])
求这个值的最大值

1.$n\sqrt{n}$做法

用一个结构体数组存因数是i的a中最大的数，因数是i的b中最大的数

struct name{
    int a,b;
}q[N];

然后遍历a和b，对于每个a[i]，试除法找出a[i]的所有因数x，将q[x].a跟a[i]取最大，b数组同理（时间复杂度 $n\sqrt{n}$）

然后再遍历每个因数i，求q[i].a* q[i].b * gcd(q[i].a,q[i].b),取最大就可以了

注意：define int long long会使时间复杂度和空间复杂度加倍，开的话过不去

#include<bits/stdc++.h>
using namespace std;
int n;
const int N=1e5+10;
typedef long long ll;
int a[N],b[N];
struct name{
	int a,b;
}q[N];
signed main(){ 
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	sort(a+1,a+1+n);
	sort(b+1,b+1+n);
	ll mx=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j*j<=a[i];j++){
			if(a[i]%j==0){
				q[j].a =max(q[j].a ,a[i]);
				if(j!=a[i]/j) q[a[i]/j].a=max(q[a[i]/j].a,a[i]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j*j<=b[i];j++){
			if(b[i]%j==0){
				q[j].b =max(q[j].b ,b[i]);
				if(j!=b[i]/j) q[b[i]/j].b=max(q[b[i]/j].b,b[i]);
			}
		}
	}
	for(int i=1;i<=a[n]&&i<=b[n];i++){
		mx=max(mx,(ll)q[i].a *q[i].b *i);
	}
	cout<<mx;
	return 0;
}

2.nlogn做法

枚举每个gcd的值g，对于每个g再枚举他的倍数i（调和级数，时间复杂度nlogn），看看a和b数组中包含的最大的i是多少

最后枚举完g的倍数之后，将a和b包含的g的最大的数相乘再乘g取最大就可以了

用map会超时(时间复杂度（O（logn）)，用unordered_map（时间复杂度O(1)）

关于调和级数：
形如 $\frac{1}{n}+\frac{2}{n}+\frac{3}{n}...+\frac{n}{n}$ 的柿子

他的最后结果趋近于 ${\ln }_{}n$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
int a[N],b[N];
typedef long long ll;
int main(){
	scanf("%d",&n);
	int mx=0;
	unordered_map<int,int> mpa;
	unordered_map<int,int> mpb;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		mx=max(mx,a[i]);
		mpa[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
		mx=max(mx,b[i]);
		mpb[b[i]]++;
	}
	ll ans=0;
	for(int g=1;g<=mx;g++){
		int am=0,bm=0;
		for(int i=g;i<=mx;i+=g){
			if(mpa[i]){
				am=max(am,i);
			}
			if(mpb[i]){
				bm=max(bm,i);
			}
		}
		ans=max(ans,(ll)am*bm*g);
	}
	printf("%lld",ans);
	return 0;
}