题目链接：
Prime Switch
Time limit: 1.000 seconds
#### 问题描述
> There are lamps (uniquely numbered from 1 to N) and K switches. Each switch has one prime number
> written on it and it is connected to all lamps whose number is a multiple of that prime number. Pressing
> a switch will toggle the condition of all lamps which are connected to the pressed switch; if the lamp
> is off then it will be on, and vice versa. You can press only one switch at one time; in other words,
> no two switches can be pressed together at the same time. If you want to press multiple switches, you
> should do it one by one, i.e. allowing the affected lamps of the previous switch toggle their condition
> first before pressing another switch.
> Initially all the lamps are off. Your task is to determine the maximum number of lamps which can
> be turned on by pressing one or more switches.
> For example, let there be 10 lamps (1 . . . 10) and 2 switches which numbers are 2 and 5 as shown
> in the following figure.
> In this example:
> • Pressing switch 2 will turn on 5 lamps: 2, 4, 6, 8, and 10.
> • Pressing switch 5 will turn on 2 lamps: 5 and 10.
> • Pressing switch 2 and 5 will turn on 5 lamps: 2, 4, 5, 6, and 8. Note that lamp number 10 will
> be turned off as it is toggled twice, by switch 2 and switch 5 (off → on → off).
> Among all possible switches combinations, the maximum number of lamps which can be turned on
> in this example is 5.
#### 输入
> The first line of input contains an integer T (T ≤ 100) denoting the number of cases. Each case begins
> with two integers in a line: N and K (1 ≤ K ≤ N ≤ 1, 000), denoting the number of lamps and
> switches respectively. The next line contains K distinct prime numbers, each separated by a single
> space, representing the switches number. You are guaranteed that the largest number among those
> switches is no larger than N.
输出
For each case, output ‘Case #X: Y ’, where X is the case number starts from 1 and Y is the maximum
number of lamps which can be turned on for that particular case.
Explanation for 2nd sample case:
You should press switch 2 and 7, such that 11 lamps will be turned on: 2, 4, 6, 7, 8, 10, 12, 16, 18,
20, and 21. There exist some other combinations which can turn on 11 lamps, but none can turn more
than 11 lamps on.
Explanation for 3rd sample case:
There is only one switch, and pressing it will turn 20 lamps on.
Explanation for 4th sample case:
Pressing all switches will turn 42 lamps on, and it is the maximum possible in this case.
样例
sample input
4
10 2
2 5
21 4
2 3 5 7
100 1
5
100 3
3 19 7sample output
Case #1: 5
Case #2: 11
Case #3: 20
Case #4: 42
题意
给你n盏灯，你有k个质数开关，每个质数开关可以控制是它的倍数的灯，每盏灯被打开奇数次才会亮，问如何控制开关使得亮的灯泡最多
题解
对于<31的质数开关，直接暴力枚举所有状态，对于>=31的开关（任意两个>=31的质数开关不可能共同控制同一盏灯），就贪心一下，如果把它开起来能激活更多的灯，就开，否则就关。
代码
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define X first
#define Y second
#define mkp make_pair
#define lson (o<<1)
#define rson ((o<<1)|1)
#define mid (l+(r-l)/2)
#define sz() size()
#define pb(v) push_back(v)
#define all(o) (o).begin(),(o).end()
#define clr(a,v) memset(a,v,sizeof(a))
#define bug(a) cout<<#a<<" = "<<a<<endl
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define scf scanf
#define prf printf
typedef long long LL;
typedef vector<int> VI;
typedef pair<int,int> PII;
typedef vector<pair<int,int> > VPII;
const int INF=0x3f3f3f3f;
const LL INFL=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-8;
const double PI = acos(-1.0);
//start----------------------------------------------------------------------
const int maxn=1111;
int n,m;
int light[maxn];
void solve(int &ret,int x){
for(int i=x;i<=n;i+=x){
light[i]^=1;
if(light[i]) ret++;
else ret--;
}
}
int main() {
int tc,kase=0;
scf("%d",&tc);
while(tc--){
scf("%d%d",&n,&m);
VI a1,a2;
rep(i,0,m){
int x; scf("%d",&x);
if(x<31) a1.pb(x);
else a2.pb(x);
}
int ans=0;
rep(i,0,(1<<a1.sz())){
clr(light,0);
int cnt=0;
rep(j,0,a1.sz()){
if((1<<j)&i){
solve(cnt,a1[j]);
}
}
rep(j,0,a2.sz()){
int tmp=0;
solve(tmp,a2[j]);
cnt+=max(0,tmp);
}
ans=max(ans,cnt);
}
prf("Case #%d: %d\n",++kase,ans);
}
return 0;
}
//end-----------------------------------------------------------------------