Reconstructing Array Elements from Multiple Summaries

An unknown array x of N integers is given. For a positive integer K the K‐summary of the array is obtained by partitioning the array sequentially into segments of length K (except possibly the last segment which might contain fewer than K elements) and replacing each segment by the sum of its elements. For example, if N = 13 and K = 5 then the segments are x[1..5], x[6..10] and x[11..13] and the 5‐summary is an array of three numbers.

Clearly, the K‐summary does not suffice to reconstruct the original array. However, if we knew several K‐summaries corresponding to different values K₁, K₂, …, K_M then some of the original elements might be uniquely determined (that is, their values would be the same in every solution of the resulting system of linear equations). It turns out that the number of uniquely determined elements is independent of the actual summary values and depends only on N and the set of K's.

Define for each segmentation parameter K the set of breakpoints as follows. Consider the K‐summary: the array is divided into segments [1, K], [K+1, 2K], …, with the last segment ending at index N. Then the breakpoints are the array indices corresponding to the endpoints in the cumulative sums. Specifically, for each K we define

$$U_K = \{0\} \cup \{K, 2K, \dots, \lfloor N/K \rfloor \cdot K\} \cup \{N\}, $$

and let U be the union of all these sets over the given K's. Now, define an element x[i] (with 1 ≤ i ≤ N) to be uniquely determined if both y[i-1] and y[i] (where y[i] = x[1]+x[2]+…+x[i] with y[0] = 0) are known from the summaries – in other words, if both indices i-1 and i appear in U. Your task is to compute the number of uniquely determined elements, i.e. the number of indices i (1 ≤ i ≤ N) for which both i-1 and i are contained in U.

Input Format

The first line contains two integers N and M, where N is the length of the original array and M is the number of summaries available. The second line contains M integers: K₁, K₂, …, K_M.

Output Format

Output a single integer: the number of elements of the original array that can be uniquely determined.

inputFormat

The input begins with a line containing two space‐separated positive integers N and M. The next line contains M space‐separated positive integers representing K₁, K₂, …, K_M.

Constraints:

• 1 ≤ N ≤ 10⁹ (note: N can be large but the union of breakpoints is small in typical cases)
• 1 ≤ M ≤ 10
• 1 ≤ K_i ≤ N

outputFormat

Output a single integer denoting the number of uniquely determined elements of the original array.

sample

13 1
5

0

</p>