变形怪

题目背景

星港实验室里关着一只变形怪。它有一种奇特的体质：只要当前体型能被某个配方整除，就能立刻把体型缩小为该配方对应的倍数。

题目描述

变形怪初始体型为 $n$。仓库里共有 $m$ 种变形配方，第 $i$ 种配方对应数值 $x_i$。

每回合变形怪可以选择任意一种配方 $i$ 尝试变形：

• 若当前体型 $v$ 能被 $x_i$ 整除，则体型变为 $v / x_i$；
• 否则该配方本次无法使用。

变形怪可以变形任意多次（包括 $0$ 次）。求变形怪一共能得到多少种不同的体型（初始体型也算一种）。

输入格式

第一行两个正整数 $n, m$。

第二行 $m$ 个正整数 $x_1, x_2, \dots, x_m$，保证两两不同。

输出格式

一行一个整数，表示能得到的不同的体型数量。

【样例 1】

【样例 1 输入】

12 2
2 3

【样例 1 输出】

6

【样例 1 解释】

可达体型为 $12, 6, 3, 4, 2, 1$，共 $6$ 种。

【样例 2】

【样例 2 输入】

30 2
5 6

【样例 2 输出】

4

【样例 2 解释】

可达体型为 $30, 6, 5, 1$（$30/5=6$，$30/6=5$，$6/6=1$，$5/5=1$），共 $4$ 种。

【样例 3】

见选手目录下的 Data/sample3.in 和 Data/sample3.ans。

该样例满足 $n \le 10^3$ 且 $m \le 4$。

【样例 4】

见选手目录下的 Data/sample4.in 和 Data/sample4.ans。

该样例满足 $x_i$ 两两互质，且 $x_i \mid n$、$x_i^2 \nmid n$。

【数据规模与约定】

对于全部数据，$1 \le n \le 10^{18}$，$1 \le m \le 8$，$2 \le x_i \le 10^6$，$x_i$ 两两不同。

【大样例下载链接】

点击下载本题选手目录