HDU 5339 Untitled （暴力枚举）

题意：给定一个序列，要求从这个序列中挑出k个数字，使得n%a1%a2%a3....=0（顺序随你意）。求k的最小值。

思路：排个序，从大的数开始模起，这是因为小的模完还能模大的么？

　　每个元素可以选，也可以不选，两种情况。递归穷举每个可能性，O(2)。

 //#include <bits/stdc++.h>

 #include <cstdio>

 #include <cstring>

 #include <map>

 #include <algorithm>

 #include <set>

 #include <iostream>

 #include <deque>

 #include <vector>

 #define INF 0x7f7f7f7f

 #define pii pair<int,int>

 #define LL unsigned long long

 using namespace std;

 const int N=;

 int a[N];

 int n, m;

 int ans;

 bool tag[N];

 void DFS(int num, int cnt)

 {

     if(num==n)

     {

         int tmp=m;

         for(int i=n-; i>=; i--)

         {

             if(tag[i])

             {

                 tmp%=a[i];

             }

         }

         if(!tmp)

         {

             ans=min(cnt, ans);

         }

         return;

     }

     tag[num]=;

     DFS(num+, cnt );

     tag[num]=;

     DFS(num+, cnt+);

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int   b, d, L, U, t, q;

     cin>>t;

     while(t--)

     {

         ans=INF;

         memset(tag,,sizeof(tag));

         scanf("%d%d", &n, &m);

         for(int i=; i<n; i++)    scanf("%d", &a[i]);

         sort(a, a+n);

         DFS(, );

         if(ans==INF)

             cout<<"-1"<<endl;

         else

             cout<<ans<<endl;

     }

     return ;

 }

AC代码