题目描述

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

题目大意

题目描述

矩阵x包括N个整数。这一矩阵的K-总和指的是将这一矩阵分割为长度为K的 区间并对每条区间中的数字求和所得的结果。如果N不能被K整除，则最后 一个区间的元素数将少于K。

换言之，K-总和指的是一个矩阵，其中的元素分别为:(x[1]+...+x[K]), (x[K+1]+...+x[2K]),以此类推。（x指的是另一个有N个元素的矩阵； K中包含了x[N]的项可以含有少于K个元素） 举例来说，一个含有十三个元素的矩阵的5-总和拥有三个元素 (x中第一到第五项之和，第六到第十项之和，第十一到第十三项之和)

显而易见的是，我们无法通过一个K-总和矩阵来重现原矩阵，但当我们知道 几个K值不同的K-总和矩阵时就可能做到这一点。输入长度N和K-总和矩阵 数量M以及K矩阵中的元素，编写一条程序，计算重现原矩阵所需要的 K-总和矩阵元素数。 （不难知道原矩阵的元素数与所需元素数无关）

输入输出格式

输入格式

第一行包含两个整数N和M（3<=N<=10^9,1<=M<=10），N为原矩阵大小，M为K-总和矩阵（区间）长度。

第二行包含M个整数，分别为K1，K2，... ，KM。

输出格式

输出重现原矩阵所需要的K-总和矩阵元素数。

感谢@Segment_Tree 提供的翻译

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].