#P5539. 【XR-3】Unknown Mother-Goose

    ID: 4835 远端评测题 2000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>O2优化枚举,暴力位运算,按位

【XR-3】Unknown Mother-Goose

题目描述

小 X 得到了一个正整数 nn 和一个正整数集合 SS,他想知道有多少个正整数 xx 满足以下所有条件:

  • 3xn3 \le x \le n
  • 存在 aS,x0(moda)a \in S, x \equiv 0 \pmod a
  • 存在 bS,x10(modb)b \in S,x-1 \equiv 0 \pmod b
  • 存在 cS,x20(modc)c \in S,x-2 \equiv 0 \pmod c

请你帮小 X 求出来。

输入格式

第一行两个正整数 n,Sn,|S|,表示你得到的 nn 和正整数集合 SS 的大小。

第二行 S|S| 个正整数,表示正整数集合 SS 中的元素。

数据范围:

  • 3n1093 \le n \le 10^9
  • 3S203 \le |S| \le 20
  • 保证 SS 中所有元素均小于 nn,不保证所有元素互不相同。

输出格式

一行一个整数,表示答案。

10 3
2 4 5

1

100000 6
14 47 31 233 666 59

91

提示

【样例 11 说明】

只有当 x=6x = 6 时:

  • x0(mod2)x \equiv 0 \pmod 2
  • x1(mod5)x \equiv 1 \pmod 5
  • x2(mod4)x \equiv 2 \pmod 4

满足条件。