/*
* hdu1796.c
*
* Created on: 2011-10-3
* Author: bjfuwangzhu
*/
#include<stdio.h>
#define LL long long
#define nmax 11
int num[nmax], nlen;
LL res;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
void dfs(int start, int c, int lcm, int n) {
int i;
lcm = lcm / gcd(lcm, num[start]) * num[start];
if (c & 1) {
res += n / lcm;
} else {
res -= n / lcm;
}
for (i = start + 1; i < nlen; i++) {
dfs(i, c + 1, lcm, n);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int n, m, mm, i, j;
while (~scanf("%d %d", &n, &m)) {
for (i = 0, nlen = 0; i < m; i++) {
scanf("%d", &mm);
if (mm > 0 && mm < n) {
num[nlen++] = mm;
}
}
res = 0;
for (j = 0; j < nlen; j++) {
dfs(j, 1, num[j], n - 1);
}
printf("%lld\n", res);
}
return 0;
}
/*
* soj3137.c
*
* Created on: 2011-10-10
* Author: bjfuwangzhu
*/
#include<stdio.h>
#define LL long long
#define nmax 11
int num[nmax];
int n, m, res, flag;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
void dfs(int start, int lcm) {
LL temp;
if (start == n) {
if (flag & 1) {
res += m / lcm;
} else if (flag > 0) {
res -= m / lcm;
}
return;
}
temp = (LL) lcm;
temp = temp / gcd(lcm, num[start]) * num[start];
flag++;
if (temp <= m) {
dfs(start + 1, temp);
}
flag--;
dfs(start + 1, lcm);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int t, i;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%d", num + i);
}
res = 0, flag = 0;
dfs(0, 1);
printf("%d\n", res);
}
return 0;
}
/*
* soj3137.c
*
* Created on: 2011-10-10
* Author: bjfuwangzhu
*/
#include<stdio.h>
#define LL long long
#define nmax 11
int num[nmax];
int n, m, res;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
void dfs(int i, LL lcm, int flag) {
int j;
lcm = lcm / gcd(lcm, num[i]) * num[i];
if (flag & 1) {
res += m / lcm;
} else {
res -= m / lcm;
}
flag++;
for (j = i + 1; j < n; j++) {
dfs(j, lcm, flag);
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int t, i;
scanf("%d", &t);
while (t--) {
scanf("%d %d", &n, &m);
for (i = 0; i < n; i++) {
scanf("%d", num + i);
}
res = 0;
for (i = 0; i < n; i++) {
dfs(i, 1, 1);
}
printf("%d\n", res);
}
return 0;
}
hdu 1796 How many integers can you find
/*
* hdu1796.c
*
* Created on: 2011-10-3
* Author: bjfuwangzhu
*/
#include<stdio.h>
#define LL long long
#define nmax 11
int num[nmax], nlen, flag;
LL res;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
void dfs(int start, int lcm, int n) {
LL temp;
if (start == nlen) {
if (flag & 1) {
res += n / lcm;
} else if (flag > 0) {
res -= n / lcm;
}
return;
}
temp = (LL) lcm;
temp = temp / gcd(lcm, num[start]) * num[start];
flag++;
if (temp <= n) {
dfs(start + 1, temp, n);
}
flag--;
dfs(start + 1, lcm, n);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
#endif
int n, m, mm, i;
while (~scanf("%d %d", &n, &m)) {
for (i = 0, nlen = 0; i < m; i++) {
scanf("%d", &mm);
if (mm > 0 && mm < n) {
num[nlen++] = mm;
}
}
res = 0, flag = 0;
dfs(0, 1, n - 1);
printf("%lld\n", res);
}
return 0;
}