|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|0.5 초||64 MB||15||9||5||62.500%|
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 + … + 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 K1, K2, …, KM, predict how many elements of the original array we would be able to uniquely determine if we knew all the Ki-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 ≤ 109, 1 ≤ M ≤ 10), the array length and the number of K-summaries.
The second line contains distinct integers K1, K2, …, KM (2 ≤ Ki < N) from the task.
You must output the required number of reconstructed elements.
3 1 2
6 2 2 3
123456789 3 5 6 9
Clarification of the first example: We can determine one element: x.
Clarification of the second example: We can determine x and x.