这道题竟然暴力能拿到90分，大佬orzorzorz%%%%%%%%%%%

--------------------------分割线（下面是正解）---------------------------------

首先还是暴力，枚举选哪些数；

然后是正解：对于N，可以将它质因数分解为(a1^p1)*(a2^p2)*……*(ai^pi)的形式，因为要两两互质，那么令U={a1^p1,a2^p2,……,ai^pi}，那么选出来的数一定是U的子集，且所有数取交为空集，取并为U，可以证明，i不会超过15，所以考虑状压DP来存储子集，转移也很简单。

贴代码：

#include
    
     #include
     
      #include
      
       using namespace std;const int N=100005;pair
       
        B[N]; long long mul,pow=1,F[1<<20],n;int mk[N],pri[N],ok[N],v[N],A[505],bit,cnt,num,m,k,tmp;void prime_shaker(){	for(int i=2;i
        
         1) 	  B[++tmp]=make_pair(x,1),v[++num]=x; 	return;}bool check(int x){	if(n%x) 	  return 0; 	divide(x);	for(int i=1;i<=tmp;i++)	{		mul=1;		for(int j=1;j<=B[i].second;j++)		  mul=mul*B[i].first;		if((n/mul)%B[i].first==0)		  return 0;	} 	return 1;}int cal(int x){	int Ret=0;	for(int i=0;i
         
          1) { puts("0"); exit(0); } return;}int main(){ prime_shaker(); scanf("%lld%d",&n,&k); for(int x,i=1;i<=k;i++) { scanf("%d",&x); if(x==1) { pow=2; continue; } if(check(x)) A[++m]=x; } sort(v+1,v+num+1); for(int i=1;i<=num;i++) if(v[i]!=v[i+1]) v[bit++]=v[i]; check_zero(); for(int i=1;i<=m;i++) A[i]=cal(A[i]); F[0]=1; for(int i=0;i<(1<