题目转化：将2~n的数分成两组，可以不选，使得这两组没有公共的质因子。求方案数。
选择了一个数，相当于选择了它的所有质因子。
30分：
发现，n<=30的时候，涉及到的质因子也就10个。2,3,5,7,11,13,19,23,29
直接状压。f[i][A][B] 前i个数，第一个人的质因子选择状态A,第二人B，的方案数。（第一维可以滚动，当然，可以倒序循环直接省略）
每个数质因数分解，前八个质因子，压成二进制数，转移直接按位或。
100分：
质因子太多状压不了。
公理：一个数>=sqrt(n)的质因子最多只有一个。（证明：反证。ax=by=n ; a,b>sqrt(n) 且a，b质数。 (a,b)=1 此时，x=b,y=a是最小的满足ax=by 的解，但是ab>n 矛盾）
所以，对于最大质因子>=sqrt(n)的数，根据最大质因子分类，质因子相同的，要么都考虑进入A，要么都考虑进入B，要么都不选。
设g[0/1][A][B]表示这一阶段，数字都考虑进入A/B的方案数。初值和f一样。
最后，f[A][B]=g[0][A][B]+g[1][A][B]-f[A][B] 因为，所有数都不选的方案计算了两次，所以减一次。
对于最大质因子<sqrt(n)的数，直接根据上面的转移就好。
统计答案时，选择A&B=0 的方案数。
具体看代码：（luogu要开O2）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500+10;
int n,mod;
struct node{
int has;
int z;
}num[N];
bool cmp(node a,node b){
return a.z<b.z;
}
ll ans;
int zh[N],cnt;
int ps[N],tot;
int vis[N];
bool in[N];
void sieve(){
for(int i=2;i<=n;i++){
if(!vis[i]){
tot++;ps[tot]=i;
vis[i]=i;
}
for(int j=1;j<=tot;j++){
if(i*ps[j]>n) break;
vis[i*ps[j]]=ps[j];
if(i%ps[j]==0) break;
}
}
}
void sol(int x){
cnt=0;
int kk=x;
for(int i=1;i<=tot;i++){
if(x%ps[i]==0){
zh[++cnt]=i;//prime‘s id
while(x%ps[i]==0) x/=ps[i];
}
}
for(int i=1;i<=cnt;i++){
if(zh[i]>8) num[kk].z=zh[i];
else num[kk].has|=(1<<zh[i]-1);
}
if(!num[kk].z) num[kk].z=1;
}
ll f[1<<8][1<<8];
ll g[2][1<<8][1<<8];
int main()
{
scanf("%d%d",&n,&mod);
sieve();
for(int i=2;i<=n;i++)sol(i);
sort(num+2,num+n+1,cmp);
f[0][0]=1;
for(int i=2;i<=n;i++){
if(num[i].z==1){
for(int A=(1<<8)-1;A>=0;A--)
for(int B=(1<<8)-1;B>=0;B--){
f[A|num[i].has][B]=(f[A|num[i].has][B]+f[A][B])%mod;
f[A][B|num[i].has]=(f[A][B|num[i].has]+f[A][B])%mod;
}
}
else{
int zz=num[i].z;
memcpy(g[0],f,sizeof f);
memcpy(g[1],f,sizeof f);
while(num[i].z==zz&&i<=n){
for(int A=(1<<8)-1;A>=0;A--)
for(int B=(1<<8)-1;B>=0;B--){
g[0][A|num[i].has][B]=(g[0][A|num[i].has][B]+g[0][A][B])%mod;
g[1][A][B|num[i].has]=(g[1][A][B|num[i].has]+g[1][A][B])%mod;
}
i++;
}
i--;
for(int A=(1<<8)-1;A>=0;A--)
for(int B=(1<<8)-1;B>=0;B--){
f[A][B]=((g[1][A][B]+g[0][A][B])%mod-f[A][B])%mod;if(f[A][B]<0) f[A][B]+=mod;
}
}
}
for(int A=0;A<=(1<<8)-1;A++)
for(int B=0;B<=(1<<8)-1;B++){
if((A&B)==0) ans=(ans+f[A][B])%mod;
}
printf("%lld",ans);
return 0;
}
总结：
这个题目其实很巧妙。
思路：
1.互质即没有公共质因子，所以选择一个数就是选择一些质因子。转化题意。
2.30分，发现质因子很小，可以直接状压。
3.100分，发现每个数>=sqrt的质因子最多只有一个。暴力分组考虑，每组内统计都放进A/B的方案。
关键的突破口还是题意的转化。以及第三点。
原文：https://www.cnblogs.com/Miracevin/p/9343974.html