upd 2021.6.18: 修改公式符号，更加形式化，添加 $50$ 分做法
upd 2022.7.30: 修改转移方程的笔误，修改公式符号
介绍一种 $O(n \times 3^8)$ 的做法，目前是所有非打表代码中的最优解，其实只是把其他题解中的算法优化了一下。
定义
- $fac_i$ 表示 $i$ 的质因数集合
- $P={x\mid x\ \text{is prime},\ x\le n}$
暴力 1
这题的暴力有很多种，在此只介绍可以优化成正解的暴力。
两个数互质，等效于他们没有共同的质因子，所以只需把每个数都分解质质因数，如下 dp：
- 状态：$dp(s_1,s_2)$ 表示考虑前 $i$ 个数（$i$ 被滚动掉了），小 G 选的数的包含的质因数集合为 $s_1$，小 W 的质因数集合为 $s_2$ 的情况数。
- 转移：
- 答案：
复杂度 $O(n\times2^{20})$，能得 $30$ 分。
暴力 2
（该部分分对正解启发不大，一笔带过）
$dp(s)$ 表示在 前 $i$ 个数中，选的数质因数集合恰好为 $s$ 的情况数。然后再算出 $dp$ 的子集和，即 $f(s)=\sum_{i \subset s} dp(i)$ ，答案便是 $\sum _{i\subset P}dp(i)f(P \setminus i)$。
仅仅这样还是不够的，因为小于一百的质数有 $25$ 个，但是发现大于 $50$ 的每个质因数只可能出现一次，所以我们可以只考虑剩下的小于等于 $50$ 的 $15$ 个质数，最后将答案乘以 $3^{\pi(n)-\pi(50)}$ 即可，可得 $50$ 分。
正解
$n \le 500$，则小于 $n$ 的质数大概有一百个了，仿佛就无法状压了。但经过仔细观察（看题解），发现每个数只可能有一个大于 $\sqrt{500}$ 的质因数，也就是说，每个数除了这个最大质因数之外，剩下的质因数都小于 $19$。
小于 $19$ 的质因数只有 $8$ 个，不难状压，所以我们只要考虑如何排除那些大质因数的干扰。
考虑将这些数按其大质因数排序，则大质因数相同的一个连续段中的每个数要么只被小 G 选或不被选，要么只被小 W 选或不被选。
考虑如下 dp：
- $dp(s_1,s_2)$ 含义与暴力 1 中的差不多，只不过这里的 $s_1$，$s_2$ 只状压了前 8 个质数的状态。
- 每次进入一个新的连续段，把 $dp$ 中的值复制到 $t_1，t_2$ 中。
- 用 $t_1(s_1,s_2)$ 表示这个连续段中的数只被小 G 选或不被选的情况数
- 用 $t_2(s_1,s_2)$ 表示这个连续段中的数只被小 W 选或不被选的情况数
- 转移：
- 这个连续段结束之后，再用 $t_1$，$t_2$ 中的值更新 $dp$ 值：
为什么要减去 $dp(s_1,s_2)$ 呢？因为这一段中所有数都不选的情况被算了两次（$t_1$，$t_2$ 各一次）。
小优化
截止目前，算法复杂度还是 $O(n \times 4^8)$ 的，但是不难发现对于一个合法状态，是要求 $s_1$，$s_2$ 交为空的。因此真正有用的状态数只有 $3^8$ 量级。 所以我们可以如下枚举 $s_1$ 和 $s_2$：
int ALL=1<<8;
for(int s1=ALL-1;~s1;s1--){//因为是滚动数组，所以集合必须从大到小枚举
int tmp=(ALL-1)^s1;//s2 必定是 tmp 的子集
for(int s2=tmp;s2;s2=(s2-1)&tmp)
//blabla...
//单独处理 s2=0 的情况
}
代码
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int> pi;
const int MXPRI=8;
const int ALL=1<<MXPRI;
const int MXN=505;
const int pri[]={2,3,5,7,11,13,17,19};
int n,p,dp[ALL][ALL],t1[ALL][ALL],t2[ALL][ALL];
pi arr[MXN];
inline int mod(int x){return x<p?x:x-p;}
int main(){
scanf("%d%d",&n,&p);
for(int i=2,j;i<=n;i++)
for(arr[i].fi=i,j=0;j<MXPRI;j++)
while(arr[i].fi%pri[j]==0)
arr[i].fi/=pri[j],arr[i].se|=1<<j;
sort(arr+2,arr+n+1);
t1[0][0]=1;
for(int i=2;i<=n;i++){
if(arr[i].fi==1 || arr[i].fi!=arr[i-1].fi)
for(int s1=ALL-1;~s1;s1--){
int tmp=(ALL-1)^s1;
for(int s2=tmp;s2;s2=(s2-1)&tmp)
t1[s1][s2]=t2[s1][s2]=dp[s1][s2]=mod(p-dp[s1][s2]+mod(t1[s1][s2]+t2[s1][s2]));
t1[s1][0]=t2[s1][0]=dp[s1][0]=mod(p-dp[s1][0]+mod(t1[s1][0]+t2[s1][0]));
}
for(int s1=ALL-1,fac=arr[i].se;~s1;s1--){
int tmp=(ALL-1)^s1;
for(int s2=tmp;s2;s2=(s2-1)&tmp){
if(!(fac&s2))t1[s1|fac][s2]=mod(t1[s1|fac][s2]+t1[s1][s2]);
if(!(fac&s1))t2[s1][s2|fac]=mod(t2[s1][s2|fac]+t2[s1][s2]);
}
t1[s1|fac][0]=mod(t1[s1|fac][0]+t1[s1][0]);
if(!(fac&s1))t2[s1][fac]=mod(t2[s1][fac]+t2[s1][0]);
}
}
int ans=0;
for(int s1=ALL-1;~s1;s1--){
int tmp=(ALL-1)^s1;
for(int s2=tmp;s2;s2=(s2-1)&tmp)
ans=mod(ans+mod(p-dp[s1][s2]+mod(t1[s1][s2]+t2[s1][s2])));
ans=mod(ans+mod(p-dp[s1][0]+mod(t1[s1][0]+t2[s1][0])));
}
printf("%d\n",ans);
return 0;
}
作者：@ethan-enhe
本文为作者原创，转载请注明出处：本文链接
阅读量: