状态压缩DP

#include<bits/stdc++.h>
using namespace std;
const int N = 22, M = 1<<N;
long long int f[M][N];
bool g[N][N];
int gcd(int a,int b)
{
    return  b==0 ? a : gcd(b,a%b);
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){ 
        for(int j=i+1;j<=n;j++){
            if(gcd(i,j)==1){
                g[i-1][j-1]=g[j-1][i-1]=true; //映射到0~20
            }
        }
    }
    f[1][0]=1;
    for(int i=0;i<1<<n;i++){
        for(int j=0;j<n;j++){
            if(i>>j&1){
                for(int k=0;k<n;k++){
                    if(i-(1<<j)>>k&1 && g[k][j]){
                        f[i][j] += f[i-(1<<j)][k];
                    }
                }
            }
        }
    }
    long long ans = 0;
    for(int i=1;i<n;i++){
        ans += f[(1<<n)-1][i];
    }
    cout<<ans;
    return 0;
}

答案:881012367360