[COCI2017-2018#3] Sažetak

题目描述 矩阵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 提供的翻译

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

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