NOIP模拟赛 乘积（容斥计数）

$n<=1e9,m<=3e5$n<=1e9,m<=3e5

题解：

具体来说就是先类莫比乌斯反演一波（这个关于倍数的莫比乌斯反演过程可以用经典的补集转化$O(n\log n)$O(nlogn)代替，于是就NOIP了），然后就变成求$d | gcd$d∣gcd的$prod$prod，然后可以分别求出每个质因数及质因数的幂的贡献然后合并，完。
注：质因数的幂注意开$long long$longlong，中间乘爆也会进for的。

$AC\ Code$AC Code:

#include<bits/stdc++.h>
#define maxn 300005
#define mod 998244353
#define md 998244352
using namespace std;

int n,m,ans=1;
int pr[maxn],cnt_pr,vis[maxn],f[maxn],g[maxn],pw[maxn];
int Pow(int base,int k,int p){
	int ret=1;
	for(;k;k>>=1,base=1ll*base*base%p)
		if(k&1)
			ret=1ll*ret*base%p;
	return ret;
}
int calc(int m){
	int ret = 1 , sum = pw[m];
	for(int i=0;i<cnt_pr && pr[i]<=m;i++){
		int t = 0;
		for(long long j=pr[i];j<=m;j*=pr[i])//!!! 129900 * 129900 -> int overflow
			t = (1ll * t + sum - pw[m - m/j]) % md;
		ret = 1ll * ret * Pow(pr[i],(t+md)%md,mod) % mod;
	}
	return ret;
}

int main(){
	scanf("%d%d",&n,&m);
	pw[1] = 1;
	for(int i=2;i<=m;i++){
		if(!vis[i]) pr[cnt_pr++] = i;
		for(int j=0;pr[j]*i<=m;j++){
			vis[i*pr[j]] = 1;
			if(i%pr[j] == 0)break;
		}
		pw[i] = Pow(i,n,md);
	}
	
	for(int i=1,nxt;i<=m;i=nxt+1){
		nxt = m/(m/i);
		int t = calc(m/i);
		for(int j=i;j<=nxt;j++)
			g[j] = 1ll * t * Pow(j,pw[m/i],mod) % mod;
	} 
	for(int i=m;i>=1;i--){
		for(int j=2*i;j<=m;j+=i)
			g[i] = (1ll * g[i] * f[j]) % mod;
		f[i] = Pow(g[i] , mod-2 , mod);
	}
	for(int i=1;i<=m;i++)
		ans = 1ll * ans * Pow(g[i],i,mod) % mod;
	printf("%d\n",(ans+mod)%mod);
}