题目传送门

分析

最小公倍数最终一定会被表示成若干个质数指数幂的情况（1的情况就直接乘上二的次幂）

然后每个数的加入相当于对每个质数的指数取最大值，但是如果将每个质数的次数都表示出来状态数很多，

考虑根号分治，只将 \(2,3,5,7,11,13,17\) 的情况处理出来，然后之后的质数幂次直接滚动数组就可以了。

代码

#include 
#include 
#include 
#include 
using namespace std;
const int N=301,mx[7]={9,6,4,3,3,3,3};
const int prime[62]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293};
int n,mod,ans,tot,c[N],a[N][7],b[N],o,rk[N],pw[7][9],p[7],_p[7],two[300011],dp[2][2][9][6][4][3][3][3][3],f[2][9][6][4][3][3][3][3];
int iut(){
	int ans=0; char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=ans*10+c-48,c=getchar();
	return ans;
}
int max(int a,int b){return a>b?a:b;}
void Mo(int &x,int y){x=x+y>=mod?x+y-mod:x+y;}
bool cmp(int x,int y){return b[x]=mod?t0+t1-mod:t0+t1);
					g=1;
					for (int j=6;g&&~j;--j)
						p[j]+=g,g=p[j]/mx[j],p[j]%=mx[j];
				}
			}
			for (int j=0;j<7;++j) p[j]=0;
			for (int g=0;!g;){
				int &t=dp[o][1][p[0]][p[1]][p[2]][p[3]][p[4]][p[5]][p[6]];
				Mo(dp[o][0][p[0]][p[1]][p[2]][p[3]][p[4]][p[5]][p[6]],1ll*t*prime[b[rk[l]]]%mod),t=0;
				g=1;
				for (int j=6;g&&~j;--j)
					p[j]+=g,g=p[j]/mx[j],p[j]%=mx[j];
			}
		}else{
			for (int i=l;i<=r;++i){
				if (!c[rk[i]]) continue;
				int t=two[c[rk[i]]]-1;
				o^=1,memcpy(f[o],f[o^1],sizeof(f[o]));
				for (int j=0;j<7;++j) p[j]=0;
				for (int g=0;!g;){
					int now=1ll*f[o^1][p[0]][p[1]][p[2]][p[3]][p[4]][p[5]][p[6]]*t%mod;
					if (now){
						for (int j=0;j<7;++j) _p[j]=max(p[j],a[rk[i]][j]);
					    Mo(f[o][_p[0]][_p[1]][_p[2]][_p[3]][_p[4]][_p[5]][_p[6]],now);
					}
					g=1;
					for (int j=6;g&&~j;--j)
						p[j]+=g,g=p[j]/mx[j],p[j]%=mx[j];
				}
			}
		}
		if (l==1&&!b[rk[1]]){
			for (int j=0;j<7;++j) p[j]=0;
			for (int g=0;!g;){
				dp[0][0][p[0]][p[1]][p[2]][p[3]][p[4]][p[5]][p[6]]=f[o][p[0]][p[1]][p[2]][p[3]][p[4]][p[5]][p[6]];
				g=1;
				for (int j=6;g&&~j;--j)
					p[j]+=g,g=p[j]/mx[j],p[j]%=mx[j];
			}
			o=0;
		}
	}
	for (int j=0;j<7;++j) p[j]=0;
	for (int g=0;!g;){
		int t=1ll*pw[0][p[0]]*pw[1][p[1]]*pw[2][p[2]]*pw[3][p[3]]%mod*pw[4][p[4]]*pw[5][p[5]]*pw[6][p[6]]%mod;
		Mo(ans,1ll*dp[o][0][p[0]][p[1]][p[2]][p[3]][p[4]][p[5]][p[6]]*t%mod);
		g=1;
		for (int j=6;g&&~j;--j)
			p[j]+=g,g=p[j]/mx[j],p[j]%=mx[j];
	}
	return !printf("%lld",1ll*ans*two[c[1]]%mod);
}