beautiful set

没啥思路，
看了题解，要用莫比乌斯反演，但是和欧拉函数结合的一部分不是很清楚
${\sum }_{i=1}^{n}phi\left[n\right]={\sum }_{i=1}^{n}d\mid nMu\left[d\right]$∑i=1n​phi[n]=∑i=1n​d∣nMu[d]

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;


typedef long long LL;
#define clr(a,x) memset(a,x,sizeof(a))

const int MAXN=100005;
const int mod=258280327;

bool prime[MAXN];
int phi[MAXN];
int cnt[MAXN];
int id[MAXN];
int f[MAXN];
int vf[MAXN];
int n;

void exgcd(int a,int b,int& x,int& y){
	if (b) {
		exgcd(b,a%b,y,x);
		y-=a/b*x;
	}
	else {
		x=1,y=0;
	}
}

int inv(int a){
	int x,y,b=mod;
	exgcd(a,b,x,y);
	if (x<0) x+=mod;
	return x;
}

int cmp(int a,int b){
	return cnt[a]>cnt[b];
}

void calc(){
	for (int i=1;i<MAXN;i++){
		id[i]=i;
	for (int j=i+i;j<MAXN;j+=i)
	 cnt[i]+=cnt[j];
	}
	sort(id+1,id+MAXN,cmp);
}


void preprocess(){
	f[0]=vf[0]=1;
	for (int i=1;i<MAXN;i++){
		phi[i]=i;
		f[i]=(LL)i*f[i-1]%mod;
		vf[i]=inv(f[i]); 
	} 
	for (int i=2;i<MAXN;i++) if (!prime[i])
	{
		for (int j=i;j<MAXN;j+=i){
			phi[j]=phi[j]/i*(i-1);
			prime[j]=1;
		} 
	}
}
int c(int a,int b){
	return (LL)f[a]*vf[b]%mod*vf[a-b]%mod;
} 

void solve(){
	int x;
	int ans1=0,ans2=0;
	clr(cnt,0);
	for (int i=1;i<=n;i++){
		scanf("%d",&x);
		cnt[x]++;
	}
	calc();
	for (int i=1;i<MAXN;i++){
		int tmp=0;
		for (int j=1;j<MAXN;j++){
		  int idx=id[j];
		  if (cnt[idx]<i) break;
		  int t=(LL)c(cnt[idx],i)*phi[idx]%mod;
		  tmp=(tmp+t)%mod;
		}
		
		ans2=(ans2+(LL)i*tmp)%mod;
		tmp=(LL)tmp*f[i]%mod*f[n-i+1]%mod;
		ans1=(ans1+tmp)%mod;
     }
     if (ans1>ans2) printf("Mr. Zstu %d\n",ans1);
     else if (ans1<ans2) printf("Mr. Hdu %d\n",ans2);
     else printf("Equal %d\n",ans1);
}
int main(){
	preprocess();
	while (~scanf("%d",&n))
      solve();
    return 0;
}