题目描述

An unknown array x consists of N integers. The K-summary of that array is obtained by dividing the array into segments of length K and summing up the elements in each segment. If N is not divisible by K, the last segment of the division will have less than K elements.

In other words, the K-summary is an array where the elements are, respectively: (x[1] + … + x[K]), (x[K+1] + … + x[2K]), and so on, where the last sum that contains x[N] can have less than K summands. For example, the 5-summary of an array of 13 elements has three elements (sum of elements 1.-5., sum of elements 6.-10., sum of elements 11.-13.).

It is clear that we cannot reconstruct the elements of the original array from the K-summary, but that might be possible if we knew several K-summaries for different Ks. Write a program that will, given length N and set $K_1$, $K_2$ , …, $K_M$ , predict how many elements of the original array we would be able to uniquely determine if we knew all the $K_i$ -summaries of the array. (It is not difficult to show that the number of reconstructed elements is independent of the content of the summaries.)

输入格式

The first line contains the integers N and M (3 <= N <= $10^9$ , 1 <= M <= 10), the array length and the number of K-summaries.

The second line contains distinct integers$K_1$, $K_2$ , …, $K_M$ (2 <= $K_i$ < N) from the task.

输出格式

You must output the required number of reconstructed elements

题目大意

题目描述

有一个长度为 $N$ 的未知数组 $x$。这个数组的 $K$-总和定义为将该数组分割为若干长度为 $K$ 的区间，并对每个区间中的元素分别求和的结果。如果 $N$ 不能被 $K$ 整除，则最后一个区间的元素数将少于 $K$。

换言之，$K$-总和指的是一个数组，其中的元素分别为：$(x_1+\dots+x_K)$，$(x_{K+1}+\dots+x_{2K})$，以此类推；其中包含了 $x_N$ 的元素，即最后一个元素，可以由少于 $K$ 个部分组成。例如，一个含有十三个元素的数组的 $5$-总和有三个元素（第一到第五项之和，第六到第十项之和，第十一到第十三项之和）

可以发现我们无法通过一个 $K$-总和来重现原数组，但当我们知道几个 $K$ 值不同的 $K$-总和时就有可能做到这一点。给定 $N$ 和 $K_1,K_2,\dots,K_M$，请您编写一条程序，计算在已知一个长为 $N$ 的数组的 $K_i$-总和的前提下，有多少原数组的元素可以被唯一确定（不难发现唯一确定的元素数与 $K_i$-总和的内容无关）。

输入格式

第一行包含两个整数 $N$ 和 $M$，$N$ 为原数组大小，$M$ 为已知 $K$-总和的数量。

第二行包含 $M$ 个整数，分别为 $K_1,K_2,\dots,K_M$，如题所述。

输出格式

您需要输出唯一确定的元素数。

数据范围

对于 $40\%$ 的数据，$N\le5\times10^6$。

对于 $100\%$ 的数据，$3\le N\le10^9$，$1\le M\le10$，$2\le K_i<N$。

样例解释

对于第一个样例：我们可以确定 $x_3$。

对于第二个样例：我们可以确定 $x_3$ 和 $x_4$。

翻译来自于 @阿丑

3 1
2

1

6 2
2 3

2

123456789 3
5 6 9

10973937

提示

In test cases worth 40% of total points, it will hold N <= 5 000 000.

Clarification​ ​of​ ​the​ ​first​ ​example:​ ​We can determine one element: x[3].

Clarification​ ​of​ ​the​ ​second​ ​example:​ ​We can determine x[3] and x[4].