---

题面

https://www.luogu.org/problemnew/show/P2150

---

题解

这道题没什么高深的知识点, 但仍然是一道极好的题.
先从部分分开始分析.

30分做法

$ n\leq30$
可以想到一个裸的状压DP, 记录

1. Dp至第几位<阶段>

2. 小G选数集合

3. 小W选数集合<对之后状态的影响>
   但是这样会有\(30*2^{60}\)种状态, 太多了
   然而题目只需要关心是否在两人选数集合中有数字不互质
   所以我们在<对之后状态的影响>中只需要记录两人拥有的数的质因子集合就可以了

复杂度最坏\(O(30*2^{16})\)

\[ 状态转移方程:\\ f[i][sta_1 | set_i][sta_2] = f[i-1][sta_1 | set_i][sta_2]+f[i-1][sta_1][sta_2]\\ f[i][sta_1][sta_2 | set_i] = f[i-1][sta_1][sta_2 | set_i]+f[i-1][sta_1][sta_2]\\ i表示当前考虑前i个数; sta_1, sta_2表示两人拥有的数的质因子集合;set_i表示整数i的质因子集合 \]

60分做法

不知道有什么做法....应该是100分算法写挂了给的部分分吧....

100分做法

虽然\(n\leq500\) , 但是我们可以发现 \(\sqrt n\lt 23\), 而大于\(\sqrt n\)的素数因子在一个数中只出现一次

所以可以把大于\(\sqrt n\)的数分块 (反正数的顺序在转移方程中也不重要是不是?)

这种按照约数进行\(\sqrt n\) 分块

https://blog.sengxian.com/solutions/bzoj-4197

(细节见代码)

总结

不该犯的错误:
位运算优先级低,必须要加括号!!!这个错误容易避免但是难调

#include<bits/stdc++.h>
using namespace std;

#define int long long 
const int primes[] = {2,3,5,7,11,13,17,19};
int n, p;
pair<int,int> num[505];
int f[505][505], g[2][505][505];
int mod(int a){
    return (a + p) % p;
}
signed main(){
    scanf("%lld%lld", &n, &p);
    
    for(int i = 1; i < n; i++){
        int digits = 0, tmp = i+1;
        for(int j = 0; j < 8; j++){
            if(tmp % primes[j] == 0) digits |= 1<<j;
            //printf("%d ",1<<j);
            while(tmp % primes[j] == 0) tmp = tmp/primes[j];
        }
        num[i].first = tmp; num[i].second = digits;
    }

    sort(num+1, num+n);
    f[0][0] = 1;
    for(int i = 1; i < n; i++){
        if(i == 1 || num[i].first==1 || num[i].first != num[i-1].first){
            for(int sta1 = (1 << 8)-1; sta1 >= 0; sta1--){
                for(int sta2 = (1 << 8)-1; sta2 >= 0; sta2--){
                    g[0][sta1][sta2] = g[1][sta1][sta2] = f[sta1][sta2];
                }
            }
        }
        
        for(int sta1 = (1 << 8)-1; sta1 >= 0; sta1--)
            for(int sta2 = (1 << 8)-1; sta2 >= 0; sta2--){
                g[0][sta1 | num[i].second][sta2] = mod(g[0][sta1 | num[i].second][sta2] + 
                    g[0][sta1][sta2]);
                g[1][sta1][sta2 | num[i].second] = mod(g[1][sta1][sta2 | num[i].second] + 
                    g[1][sta1][sta2]);
            }
        if(i == n-1 || num[i].first == 1 || num[i].first != num[i+1].first){
            for(int sta1 = (1 << 8)-1; sta1 >= 0; sta1--)
                for(int sta2 = (1 << 8)-1; sta2 >= 0; sta2--){
                    f[sta1][sta2] = mod(g[0][sta1][sta2] + g[1][sta1][sta2] - f[sta1][sta2]);
                }
        }
    }
    
    int ans = 0;
    for(int sta1 = (1 << 8)-1; sta1 >= 0; sta1--)
        for(int sta2 = (1 << 8)-1; sta2 >= 0; sta2--){
            if((sta1 & sta2) != 0) continue;
            ans = mod(ans + f[sta1][sta2]);
        }
    printf("%lld\n", ans);
    return 0;
}