Prime Multiples

题目描述

给定 $k$ 个不同的质数 $a_1,a_2,\ldots,a_k$ 和一个整数 $n$。 你的任务是计算在前 $n$ 个正整数中，有多少个数能被至少一个给定的质数整除。

输入格式

第一行输入有两个整数 $n$ 和 $k$。 第二行有 $k$ 个质数 $a_1,a_2,\ldots,a_k$。

输出格式

输出一个整数：区间 $1,2,\ldots,n$ 中能够被至少一个给定质数整除的整数个数。

20 2
2 5

12

提示

$1 \le n \le 10^{18}$ $1 \le k \le 20$ $2 \le a_i \le n$ 样例解释：这 12 个数是 2,4,5,6,8,10,12,14,15,16,18,20。

标签: CSES2185|数学

来源

CSES2185|数学