https://www.lydsy.com/JudgeOnline/problem.php?id=4197
https://www.luogu.org/problemnew/show/P2150
这题的难点就在思维了（然而我就少脑子），只要你想到压位质数的话，这道题就迎刃而解了。
参考：https://www.luogu.org/blog/larryzhong/solution-p2150
设f[i][j][k]表示到第i个寿司，G取的寿司的质因子集合为j，W为k。
不难想到dp的转移方程。
但是n是<=500的啊，其质数应该会有很多啊我们也压不过来啊。
考虑到一个数只有一个大于sqrt(n)的质因子，所以我们惊奇的发现，我们只需要压8个小于sqrt(n)的质因子即可，对于那个多出来的质数我们额外考虑就行了。
我们先对每个数的大因子排个序，则：
设g[i][0/1][j][k]表示当前处理大因子为i，j有大因子/k有大因子，G取的寿司的质因子集合为j，W为k。
转移方程基本同f。
将相同i的数处理完之后再把g放到f里。
f[j][k]=g[0][j][k]+g[1][j][k]-f[j][k]
（其中多减掉的那个原因是我们把两个集合都不取大因子i的情况算了两遍。）
（注意到f和g的第一维都可以省略。）
那么答案就是j和k不互相包含的f的总和。
#include<cmath>
#include<queue>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=;
const int B=;
const int M=<<B;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct num{
int a,b;
}s[N];
int pri[B]={,,,,,,,};
int n,p,f[M][M],g[][M][M];
inline bool cmp(num a,num b){
return a.b<b.b;
}
int main(){
n=read(),p=read();
for(int i=;i<=n;i++){
int tmp=i;
for(int j=;j<B;j++){
while(tmp%pri[j]==){
tmp/=pri[j];
s[i].a|=(<<j);
}
}
if(tmp>)s[i].b=tmp;
}
sort(s+,s+n+,cmp);
f[][]=;
for(int i=;i<=n;i++){
if(i==||(!s[i].b)||s[i].b!=s[i-].b){
memcpy(g[],f,sizeof(f));
memcpy(g[],f,sizeof(f));
}
for(int j=M-;j>=;j--){
for(int k=M-;k>=;k--){
(g[][j|s[i].a][k]+=g[][j][k])%=p;
(g[][j][k|s[i].a]+=g[][j][k])%=p;
}
}
if(i==n||(!s[i].b)||s[i].b!=s[i+].b){
for(int j=M-;j>=;j--){
for(int k=M-;k>=;k--){
f[j][k]=((g[][j][k]+g[][j][k]-f[j][k])%p+p)%p;
}
}
}
}
int ans=;
for(int j=;j<M;j++){
for(int k=;k<M;k++){
if(!(j&k))(ans+=f[j][k])%=p;
}
}
printf("%d\n",ans);
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++