给定一个整数列表 (A_1,A_2,\ldots,A_n)(A 1 ​ ,A 2 ​ ,…,A n ​ ) 和一个正整数 MM，请找出不大于 MM 且可被给定列表中任何一个整数整除的正整数的数量。给出此题的C++代码

对于这个问题，可以用暴力枚举的方法，从1到M枚举每一个数，对于每一个数再从列表中枚举每一个数，判断是否存在一个数可以整除这个枚举的数，如果存在，计数器加1。以下是相应的C代码：

#include <stdio.h>

int main() {
int n, m;
scanf("%d %d", &n, &m);
int a[n];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
int cnt = 0;
for (int i = 1; i <= m; i++) {
for (int j = 0; j < n; j++) {
if (i % a[j] == 0) {
cnt++;
break;
}
}
}
printf("%d\n", cnt);
return 0;
}

相关问题

给定一个整数列表 (A_1,A_2,\ldots,A_n)(A 1 ​ ,A 2 ​ ,…,A n ​ ) 和一个正整数 MM，请找出不大于 MM 且可被给定列表中任何一个整数整除的正整数的数量

你好，感谢你的提问。

针对你的问题，可以使用容斥原理来解决。具体地，设整数列表中的最大值为 K，那么我们可以枚举每个可行的正整数 x，其必须满足 x 是 K 的倍数。那么 x 可以表示为 y × K，其中 y 为正整数。

我们需要求的是不大于 M 且可被给定列表中任何一个整数整除的正整数的数量，可以表示为：

N(M) = \sum_{i=1}^{\lfloor M/K \rfloor} \left\lfloor \frac{M}{iK} \right\rfloor

其中 \lfloor x \rfloor 表示不大于 x 的最大整数。此时，N(M) 表示不大于 M 且可被任意一个整数整除的正整数的数量。

但是，上述方法不考虑重复计算，即同一个正整数可能会被统计多次。因此，我们需要使用容斥原理来解决这个问题。具体地，设 S(A) 表示 A 中的元素的最小公倍数，那么我们需要求的数量可以表示为：

N(M) = \sum_{S(A) \leq M} (-1)^{|A|+1} \left\lfloor \frac{M}{S(A)} \right\rfloor

其中 |A| 表示 A 中元素的个数。上式中，利用了容斥原理的思想，对于任意的集合 A，我们需要将能够整除 A 中所有元素的正整数贡献到一次，因此需要使用交替和的形式进行表示。

综上所述，我们可以设计如下的算法，求出不大于 M 且可被给定列表中任意一个整数整除的正整数的数量：

- 令 ans = 0；
- 对于每个子集 A_i，计算 S(A_i)；
- 对于每个 S(A_i) 不大于 M，计算 (-1)^{|A_i|+1} \left\lfloor \frac{M}{S(A_i)} \right\rfloor 并加入 ans；
- 返回 ans。

希望能够对你有所帮助。

给定一个正整数 nn，请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位（不含前导 00）。x!x! 表示 xx 的阶乘，即 1*2*3*\ldots*x1∗2∗3∗…∗x。 【输入格式】 给定一个正整数 nn，请计算 S = 1!+2!+3!+\ldots+n!S=1!+2!+3!+…+n! 的末 66 位（不含前导 00）。x!x! 表示 xx 的阶乘，即 1*2*3*\ldots*x1∗2∗3∗…∗x。 【输入格式】

输入包含一个正整数 n（1≤n≤1091≤n≤109）。 【输出格式】 输出一个整数，表示 S 的末 66 位。 【输入样例】 5 【输出样例】 874166702539019172 我们可以先算出每个数的末6位，然后再累加。由于一个数的末6位只与它的末3位有关，因此我们可以先预处理出1!到n!的末3位，然后再计算末6位。具体地，我们可以将每个数拆成一个后缀和一个前缀，其中前缀是一个6的倍数，后缀的位数不超过3。那么每个数对应的后缀就是其末3位的阶乘，而前缀只有4种情况，即0,6,12,18。我们可以将1!到n!按照前缀分类，然后对于每种前缀单独计算后缀的乘积，最后再将所有结果累加即可得到答案。时间复杂度为O(logn)。