Problem surface

meaning of the title

Give n, select some numbers in 2~n, divide them into two groups, so that there are no two numbers a, B, belong to these two groups respectively, and gcd(a,b)=1, there are several kinds of partition methods

practice

First of all, the question meaning can be converted into two groups of numbers, so that there is no same prime factor between the two groups. Therefore, we can consider to choose some prime factors to be divided into two groups, but n < = 500, among which there are about 100 prime factors, which cannot be converted into pressure. However, we can find that among all the prime factors of numbers less than or equal to 500, there is at most one prime number greater than 19, and there are only eight prime numbers within 19, so We can compress these eight prime numbers and consider the large prime numbers separately.
When dp is used, two arrays F1 and F2 are recorded, which respectively represent the contribution of not putting the large prime number under consideration in group B and group A (therefore, it needs to be de duplicated when merging later, that is, dp = F1 + F2 dp, dp refers to the contribution when the large prime number is not considered). Then each time before considering a large prime number (or the number without the large prime number), the value of dp is assigned to F1 and F2, and all the numbers containing the large prime number are considered Then, the values of F1 and F2 are added into dp by the above method.

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
#define N 510
#define MN 255
#define ZY 300
using namespace std;

ll n,M,ans,dp[ZY][ZY],f1[ZY][ZY],f2[ZY][ZY],zs[10]= {2,3,5,7,11,13,17,19};
bool flag;
struct Num
{
    ll zt,big;
    void in(ll u)
    {
        ll i,j;
        for(i=0; i<8; i++)
        {
            if(u%zs[i]) continue;
            zt|=(1 << i);
            for(; u%zs[i]==0; u/=zs[i]);
        }
        big=u;
    }
    bool operator < (const Num &u) const
    {
        return big<u.big;
    }
} num[N];

int main()
{
    ll i,j,k;
    cin>>n>>M;
    for(i=2; i<=n; i++) num[i].in(i);
    sort(num+2,num+n+1);
    dp[0][0]=1;
    for(i=2; i<=n; i++)
    {
        if(i==2 || num[i].big==1 || num[i].big!=num[i-1].big)
        {
            memcpy(f1,dp,sizeof(dp));
            memcpy(f2,dp,sizeof(dp));
        }
        for(j=MN;j>=0;j--)
        {
            for(k=MN;k>=0;k--)
            {
                if(j&k) continue;
                if((num[i].zt&k)==0) f1[j|num[i].zt][k]+=f1[j][k],f1[j|num[i].zt][k]%=M;
                if((num[i].zt&j)==0) f2[j][k|num[i].zt]+=f2[j][k],f2[j][k|num[i].zt]%=M;
            }
        }
        if(i==n || num[i].big!=num[i+1].big || num[i].big==1)
        {
            for(j=MN;j>=0;j--)
            {
                for(k=MN;k>=0;k--)
                {
                    if(j&k) continue;
                    dp[j][k]=f1[j][k]+f2[j][k]-dp[j][k]+M;
                    dp[j][k]%=M;
                }
            }
        }
    }
    for(i=MN;i>=0;i--)
    {
        for(j=MN;j>=0;j--)
        {
            if(i&j) continue;
            ans+=dp[i][j];
            ans%=M;
        }
    }
    cout<<ans;
}