「FJWC2020Day5-zzq」lg

设模数为$P$

考虑对于每一个$\gcd$计算$\text{lcm}$之积$F(m)$

那么可以想到强制每个数都是$\gcd$的倍数，问题转化为求$\lfloor \frac{m} {gcd}\rfloor $以内所有$\text{lcm}$的积$G(m)$

那么对于每个质因数依次考虑,则得到一个简单的式子

$$G(m)=\begin{aligned}\prod p_i^{\sum_{j=1}m^n-(m-\lfloor \frac{m} {p_i^j}\rfloor )^n} \end{aligned}$$

其中枚举的$j$是$p_i$至少出现$j$次的方案数，枚举的$j$是$\log m$ 级别的

肯定是先求出指数$\mod \varphi(P)$，可以线性预处理出所有的$i^n \mod \varphi(P)$

对于每个$p_i$求出指数后还要快速幂，复杂度就是$O(|p_i|\log P)=O(m)$，实际带有一些常数

那么求$G(m)$的复杂度上界是$O(m\log m)$，实际上$\lfloor \frac{m} {i}\rfloor $有很多重复，复杂度要低很多

得到的每个$\gcd$的答案还要把强制取出的$\gcd$补上，是$\gcd^{ {\lfloor \frac{m} {gcd}\rfloor }^n}$

那么对于$G(m)$枚举倍数进行容斥的到$F(m)$即可，需要求每个$F(m)$的逆元，复杂度是$O(m(\log P+\log m))$

总复杂度的上界就是$O(m\log P)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(int i=a;i<=b;++i)
enum{N=200010,P=998244353,Phi=P-1};
int n,m,p[N],mk[N],g[N],ig[N],h[N];
ll qpow(ll x,ll k,ll P) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int G(int m) {
	if(h[m]) return h[m];
	ll ans=1;
	rep(i,2,m) if(!mk[i]) {
		ll d=1,s=0;
		for(;(d*=i)<=m;) s+=p[m]-p[m-m/d]; // 带入上式求出答案
		ans=ans*qpow(i,(s%Phi+Phi)%Phi,P)%P;
	}
	return h[m]=ans;
}
int main(){
	freopen("lg.in","r",stdin),freopen("lg.out","w",stdout);
	scanf("%d%d",&n,&m);
	rep(i,2,N-1) if(!mk[i]) for(int j=i+i;j<N;j+=i) mk[j]=1;
	rep(i,0,m) p[i]=qpow(i,n,Phi); // 预处理出i^n mod Phi
	rep(i,1,m) g[i]=G(m/i)*qpow(i,p[m/i],P)%P; // 注意要补上
	ll ans=1;
	for(int i=m;i;i--){
		for(int j=i+i;j<=m;j+=i) g[i]=1ll*g[i]*ig[j]%P; // 容斥得到f
		ig[i]=qpow(g[i],P-2,P),ans=ans*qpow(g[i],i,P)%P;
	}
	printf("%lld\n",ans);
}