模拟赛T1DP写法 TLE求助

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4+5;
const ll mod =998244353;

int n,m;
ll p[N];
ll tabl[N];
int len;
ll dpz[N][70];
ll dpm[N][70];
ll a[N];
ll tt[70][70];
int get(int x){
	int tj=0;
	int i=1;
	for(;i*i < x;i ++)
		if(x%i==0)tj+=2;
	if(i*i==x)tj++;
	return tj;
}
void pre(){
	for(int i = 1;i <= m;i++){
		if(m%i==0)tabl[++len]=i;
	}
}
ll ans = 1;
ll zi,mu;
void ad(ll x,ll c){
	mu = get(x);
	zi = get(x*c);
	ll g= __gcd(mu,zi);
	mu/=g,zi/=g; 
}
ll quipow(ll x){
	if(x==1)return 1;
	ll a=x,b=mod-2,anss=1;
	while(b){
		if(b&1)b^=1,anss*=a,anss%=mod;
		else b>>=1,a*=a,a%=mod;
	}
	return anss;
}
 
int main(){
	cin >> n >> m;
	for(int i = 1;i <= n;i++){
		cin >>p[i];
		a[i]=get(p[i]);
		ans*=a[i];
		ans%=mod;
	}
	pre();
	for(int j =1;j<=len;j++)
	dpm[0][j]=dpz[0][j]=1;
	for(int i = 1;i <= n;i++){
		for(int j=1;j<=len;j++){
			dpm[i][j]=1;
			for(int k =1;k<=j;k++){
				if(tabl[j]%tabl[k]!=0)continue;
				ll adds=tabl[j]/tabl[k];
				ad(p[i],adds);
				double zz=(double)dpz[i-1][k]/dpm[i-1][k];
				double nz=(double)zi/mu;
				double nowz=(double)dpz[i][j]/dpm[i][j];
				if(zz*nz >nowz){
					dpz[i][j]=zi*dpz[i-1][k],dpm[i][j]=mu*dpm[i-1][k];
					ll g=__gcd(dpz[i][j],dpm[i][j]);
					dpz[i][j]/=g;
					dpm[i][j]/=g;
				}
			}
				
		}
	}
	
	cout << (((ans*dpz[n][len])%mod)*quipow(dpm[n][len]))%mod;

	
	return 0;
}