#CS2185. 质数倍数

质数倍数

题目背景

翻译自 CSES-2185 题。

题目描述

给定 k 个不同的质数 a1,a2,…,aka_1, a_2, \dots, a_ka1​,a2​,…,ak​ 和一个整数 n。

你的任务是计算在前 n 个正整数中，有多少个数能被至少一个给定的质数整除。

输入格式

第一行包含两个整数 n 和 k。

第二行包含 k 个质数 a1,a2,…,aka_1, a_2, \dots, a_ka1​,a2​,…,ak​。

输出格式

输出一个整数：表示在区间 1,2,…,n1, 2, \dots, n1,2,…,n 中，能被至少一个给定的质数整除的整数个数。

样例

20 2
2 5

12

样例1解释： 能够被 2 或 5 整除的数有：2,4,5,6,8,10,12,14,15,16,18,202, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 202,4,5,6,8,10,12,14,15,16,18,20，一共有 121212 个。

说明/提示

$1 \leq n \leq 10^{18}$

$1 \leq k \leq 20$

2≤ai≤n2 \leq a_i \leq n2≤ai​≤n。