Description:

有两个人在 $2\dots N$ 中选数，问有多少种方案使得不存在一个人手中的数与另一个人手中的数不互质，每个人可以选多个，也可以不选。

$1 \le N \le 500$

Solution:

思考一下发现，如果选了一个数，相当于选了他的质因子集合，不难想出这样一个 $DP$ ： $f[i][j]$ 表示第一个人选了质因子集合为 $i$ ，第二个人选了质因子集合为 $j$ ，显然当 $i \&j\neq0$ 时， $f[i][j]=0$ ，但发现 $500$ 以内的素数有 $95$ 个，显然是压不下的，又思考一下发现对于每个数一定只有不多于一个大于 $\sqrt{500}$ 的素因子，而小于 $\sqrt{500}$ 的素因子只有 $8$ 个，而且对于一个素因子只能被一个人选走，对于没有大于 $\sqrt{500}$ 素因子的数提前计算，其他数按照大于 $\sqrt{500}$ 的素因子分类，对于同一类中的数一定只会给一个人，建立两个辅助数组 $g[0/1][i][j]$ 表示当前一类数都给第 $1/2$ 个人的方案数，转移很好写，但两个人都不选的情况被统计了两次，最后用 $g$ 更新 $f$ 时要注意减掉两个人都不选的情况，即 $f[i][j] = g[0][i][j]+g[1][i][j]-f[i][j]$ ，因为此时 $f[i][j]$ 是更新之前的值，也就只两个都不选的情况。

最后还要注意转移顺序的问题，因为每个数只能选一次，转移时的过程有点类似于跑一个 $01$ 背包，所以应该在外层循环数字（物品），在内层倒序循环。

Code:

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cstring>

using namespace std;

typedef long long ll; 

#define MAXN 510

#define MAXB 9

int prime[MAXN],totn = 0;

int to[MAXN];

bool isprime[MAXN];

int maxdiv[MAXN];

int bit[MAXN];

vector<int> v[MAXN];

ll n,p;

ll f[1 << MAXB][1 << MAXB];

ll g[2][1 << MAXB][1 << MAXB];

void updata(ll &x,ll y){x = (x + y) % p;return;} 

void sieve()

{

    memset(isprime,0,sizeof(isprime));

    for(int i = 2;i <= 500;++i)isprime[i] = true;

    for(int i = 2;i <= 500;++i)

    {

        if(isprime[i])

        {

            prime[++totn] = i;

            to[i] = totn;

            maxdiv[i] = i;

        }

        for(int j = 1;j <= totn && i * prime[j] <= 500;++j)

        {

            isprime[i * prime[j]] = false;

            maxdiv[i * prime[j]] = max(maxdiv[i],prime[j]);

            if(i % prime[j] == 0)break;

        }

    }

    return;

}

int main()

{

    cin >> n >> p;

    sieve();

    int block = prime[8];

    for(int i = 2;i <= n;++i)

	{

	    if(maxdiv[i] > block)

	    {

			bit[i] = bit[i / maxdiv[i]];

            v[to[maxdiv[i]]].push_back(i);

        }

        else

        {

            bit[i] = (bit[i / maxdiv[i]] | (1 << (to[maxdiv[i]] - 1)));

            v[0].push_back(i);

        }

    }

    f[0][0] = 1;

    int tot = (1 << 8) - 1;

    for(int i = 0;i < v[0].size();++i)

    {

        for(int k1 = tot;k1 >= 0;--k1)

        {

            for(int k2 = tot;k2 >= 0;--k2)

            {

                if(k1 & k2)continue;

                if(!(bit[v[0][i]] & k2))

                {

                	updata(f[k1 | bit[v[0][i]]][k2],f[k1][k2]);

                }

            	if(!(bit[v[0][i]] & k1))

                {

                    updata(f[k1][k2 | bit[v[0][i]]],f[k1][k2]);

                }

            }

        }

    }

    for(int i = 9;i <= totn;++i)

    {

        memcpy(g[0],f,sizeof(f));

        memcpy(g[1],f,sizeof(f));

		for(int j = 0;j < v[i].size();++j)

		{

        	for(int k1 = tot;k1 >= 0;--k1)

	        {

    	        for(int k2 = tot;k2 >= 0;--k2)

        	    {

            	    if(k1 & k2)continue;

    	            if(!(bit[v[i][j]] & k2))

        	        {

            	        updata(g[0][k1 | bit[v[i][j]]][k2],g[0][k1][k2]);

              	    }

                   	if(!(bit[v[i][j]] & k1))

	                {

                        updata(g[1][k1][k2 | bit[v[i][j]]],g[1][k1][k2]);

       	            }

            	}

        	}

    	}

        for(int k1 = 0;k1 <= tot;++k1)

        {

            for(int k2 = 0;k2 <= tot;++k2)

            {

                f[k1][k2] = (g[0][k1][k2] + g[1][k1][k2] - f[k1][k2] + p) % p;

            }

        }

    }

    ll ans = 0;

    for(int k1 = 0;k1 <= tot;++k1)

    {

        for(int k2 = 0;k2 <= tot;++k2)

        {

			ans += f[k1][k2];

			ans %= p;

	    }

	}

    cout << ans << endl;

    return 0;

}