题目描述

n ≤ 10^8 ，m ≤ 200000

题解

没做过在指数上搞事的数论题

\(\huge ans=\prod{lcm^{gcd}}\)

\(\huge =\prod{lcm^{\sum_{d|xi}\varphi(d)}}\)

\(\huge =\prod_{d}(lcm_{xi<=m/d}*d)^{\varphi(d)}\)

\(\huge =\prod_{d}(lcm_{xi<=m/d})*d^{(m/d)^n\varphi(d)}\)

后面的直接算，前面的lcm：

\(lcm_{xi<=m/d}=\prod_{d \& d∈prime}d^{\sum_kk*((m-\frac{m}{d^{k+1}})^n-(m-\frac{m}{d^{k}})^n)}\)

意思是枚举质因子d以及次数k，要求lcm中d的次数=k的个数

这个东西等于<=k+1的个数-<=k的个数，其中<=k的又等于n个数中没有>k的（共m/(d^k)个），即(m-m/(d^k))^n

m/d只用算√m种，时间复杂度不知道是多少大概是O(n ln^2)？

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define mod 998244353
#define Mod 998244351
#define ll long long
#define file
using namespace std;

int p[200001],n,m,i,j,k,l,len,ls;
ll phi[200001],lcm,ans;
bool f[200001];

ll qpower(ll a,int b,int MOD) {ll ans=1;while (b) {if (b&1) ans=ans*a%MOD;a=a*a%MOD;b>>=1;} return ans;}

void init()
{
	int i,j,k,l;
	
	phi[1]=1;
	fo(i,2,m)
	{
		if (!f[i]) p[++len]=i,phi[i]=i-1;
		
		fo(j,1,len)
		if (1ll*i*p[j]<=m)
		{
			f[i*p[j]]=1;
			
			if (!(i%p[j])) {phi[i*p[j]]=phi[i]*p[j];break;}
			phi[i*p[j]]=phi[i]*(p[j]-1);
		}
		else break;
	}
}

ll Lcm(int m)
{
	ll ans=1,sum,P;
	int i,j,k,l;
	
	fo(i,1,len)
	if (p[i]<=m)
	{
		sum=0;P=1;
		fo(j,1,m)
		{
			P*=p[i];
			if (P>m) break;
			sum=(sum+1ll*j*(qpower(m-(m/(P*p[i])),n,mod-1)-qpower(m-(m/P),n,mod-1)))%(mod-1);
		}
		sum=(sum+(mod-1))%(mod-1);
		ans=ans*qpower(p[i],sum,mod)%mod;
	}
	else break;
	return ans;
}

int main()
{
	freopen("lg.in","r",stdin);
	#ifdef file
	freopen("lg.out","w",stdout);
	#endif
	
	scanf("%d%d",&n,&m);
	init();
	
	ans=1;
	fo(i,1,m)
	{
		if (m/i!=ls) ls=m/i,lcm=Lcm(m/i);
		ans=(ans*qpower(lcm,phi[i],mod)%mod*qpower(i,1ll*phi[i]*qpower(m/i,n,mod-1)%(mod-1),mod))%mod;
	}
	printf("%lld\n",ans);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
}