排斥定理

Teemo's dream

Teemo decides to use his money to conquer the universe.

It is known that there are m planets that humans can reach at present. They are numbered from 1 to m. Teemo bought n kinds of gateways. Their IDs are a1, a2, ..., an, the gateway whose ID is ai can transmit Teemo to the stars numbered ai,2ai, 3ai, ..., k*ai (1<=k*ai<=m, k is a positive integer), now Teemo wants to know, how many planets can he reach?

Input Format

On the firstline one positive number: the number of test cases, at most 20. After that per test case:

One line contains two integers n and m, (1 <= n <= 15, 1<= m < = 1e9), respectively represent the number of the gateway, the number of the stars that humans can reach.

One line contains n integers, the i-th integer a[i], indicating that the ID of the i-th gateway is a[i], (2<=a[i]<=1e9).

Ouput Format

Per test case:

One line contains an integer, which indicates how many planets Teemo can reach at most.

样例输入

样例输出

10
74

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 int t, n;
 5 ll m, a[20];
 6 int main() {
 7     cin >> t;
 8     while(t--) {
 9         cin >> n >> m;
10         for(int i = 0; i < n; i ++) cin >> a[i];
11         ll ans = 0;
12         for(int state = 1; state < (1<<n); ++state) {
13             ll cnt = 0, _lcm = 1;
14             for(int i = 0; i < n; i ++) {
15                 if(state&(1<<i)) {
16                     _lcm = _lcm/__gcd(a[i],_lcm)*a[i];
17                     cnt ++;
18                     if(_lcm > m) break;
19                 }
20             }
21             ans += cnt%2 ? m/_lcm: -m/_lcm;
22         }
23         cout << ans << endl;
24     }
25     return 0;
26 }