Mister B and Astronomers

题意翻译

外星球每隔T秒中只有一秒可以被观测到，其它T-1秒无法被观测。n个天文学家（分别编号为1,...,n）轮流观测天空1秒，且第i+1个科学家在第i个天文学家后ai+1秒后才执行观测，而第一个天文学家则在第n个天文学家后a1秒后才执行观测，且第一个天文学家在0秒时执行第一次观测（即第一个天文学家观测的时间是[0,1)，第二个科学家在[a2,a2+1)时观测，而最后一个天文学家在[a2+a3+...+an-1,a2+a3+...+an-1+1)时观测，之后再过a1秒后第一个天文学家继续观测）。 　　由于外星球具体在首次观测之后的T秒中的哪一秒出现是不确定的，若外星球在[i, i+1)时出现（0<=i<T-1），且天文学家j是首个观测到星球的人，则称j抢占了[i,i+1)时间片段。也就是说,如果把所有的观测时间模T之后,最先观测到时间片段[i,i+1)将占有这个时间片段。 问每个天文学家所占有的时间片段各是多少。 T <= 1e9, n <= 2e5, ai <= 1e9 例如， T = 4,n = 2, a1 = 2, a2 = 3 第一个天文学家观测的时间点是t=0,5,10,……，第二个天文学家是t=3,8,13,…… 第一个天文学家在 t=0 时占有 [0,1), 在 t=5 时占有[1,2), 在 t=10 时占有[2,3) 第二个天文学家在 t=3 时占有 [3,4)

题目描述

After studying the beacons Mister B decided to visit alien's planet, because he learned that they live in a system of flickering star Moon. Moreover, Mister B learned that the star shines once in exactly $ T $ seconds. The problem is that the star is yet to be discovered by scientists. There are $ n $ astronomers numerated from $ 1 $ to $ n $ trying to detect the star. They try to detect the star by sending requests to record the sky for $ 1 $ second. The astronomers send requests in cycle: the $ i $ -th astronomer sends a request exactly $ a_{i} $ second after the $ (i-1) $ -th (i.e. if the previous request was sent at moment $ t $ , then the next request is sent at moment $ t+a_{i} $ ); the $ 1 $ -st astronomer sends requests $ a_{1} $ seconds later than the $ n $ -th. The first astronomer sends his first request at moment $ 0 $ . Mister B doesn't know the first moment the star is going to shine, but it's obvious that all moments at which the star will shine are determined by the time of its shine moment in the interval $ [0,T) $ . Moreover, this interval can be split into $ T $ parts of $ 1 $ second length each of form $ [t,t+1) $ , where $ t=0,1,2,...,(T-1) $ . Mister B wants to know how lucky each astronomer can be in discovering the star first. For each astronomer compute how many segments of form $ [t,t+1) $ ( $ t=0,1,2,...,(T-1) $ ) there are in the interval $ [0,T) $ so that this astronomer is the first to discover the star if the first shine of the star happens in this time interval.

输入输出格式

输入格式

The first line contains two integers $ T $ and $ n $ ( $ 1<=T<=10^{9} $ , $ 2<=n<=2·10^{5} $ ). The second line contains $ n $ integers $ a_{1},a_{2},...,a_{n} $ ( $ 1<=a_{i}<=10^{9} $ ).

输出格式

Print $ n $ integers: for each astronomer print the number of time segments describer earlier.

输入输出样例

输入样例 #1

4 2
2 3

输出样例 #1

3 1 

输入样例 #2

5 4
1 1 1 1

输出样例 #2

2 1 1 1 

说明

In the first sample test the first astronomer will send requests at moments $ t_{1}=0,5,10,... $ , the second — at moments $ t_{2}=3,8,13,... $ . That's why interval $ [0,1) $ the first astronomer will discover first at moment $ t_{1}=0 $ , $ [1,2) $ — the first astronomer at moment $ t_{1}=5 $ , $ [2,3) $ — the first astronomer at moment $ t_{1}=10 $ , and $ [3,4) $ — the second astronomer at moment $ t_{2}=3 $ . In the second sample test interval $ [0,1) $ — the first astronomer will discover first, $ [1,2) $ — the second astronomer, $ [2,3) $ — the third astronomer, $ [3,4) $ — the fourth astronomer, $ [4,5) $ — the first astronomer.

题意翻译

### 题目描述 外星球每隔 $T$ 秒中只有一秒可以被观测到，其它 $T-1$ 秒无法被观测。 $n$ 个天文学家（分别编号为 $1,\ldots,n$）轮流观测天空 $1$ 秒，且第 $i+1$ 个科学家在第 $i$ 个天文学家后 $a_i+1$ 秒后才执行观测，而第一个天文学家则在第 $n$ 个天文学家后 $a_1$ 秒后才执行观测，且第一个天文学家在 $0$ 秒时执行第一次观测（即第一个天文学家观测的时间是 $[0,1)$ ，第二个科学家在 $[a_2,a_2+1)$ 时观测，而最后一个天文学家在 $[\sum^{n-1}_{i=2}a_i,1 + \sum^{n-1}_{i=2}a_i)$ 时观测，之后再过 $a_1$ 秒后第一个天文学家继续观测）。 由于外星球具体在首次观测之后的 $T$ 秒中的哪一秒出现是不确定的，若外星球在 $[i,i+1)$ 时出现（$0\le i<T-1$），且天文学家 $j$ 是首个观测到星球的人，则称 $j$ 抢占了 $[i,i+1)$ 时间片段。也就是说,如果把所有的观测时间模 $T$ 之后,最先观测到时间片段 $[i,i+1)$ 将占有这个时间片段。 问每个天文学家所占有的时间片段各是多少。 ### 输入格式 第一行两个整数 $T,n$。 第二行 $n$ 个整数表示 $a_1,a_2,\ldots,a_n$。 ### 输出格式 一行，$n$ 个整数，第 $i$ 个表示第 $i$ 个天文学家占有的时间片段数量。 ### 说明/提示 #### 数据范围 $1\leq T\le10^9$，$2\leq n\le2\times10^5$，$1\leq a_i\le10^9$。 #### 样例 1 解释 $T=4$，$n=2$，$a_1=2$，$a_2=3$。 第一个天文学家观测的时间点是 $t=0,5,10,\ldots$，第二个天文学家是 $t=3,8,13,\ldots$。 第一个天文学家在 $t=0$ 时占有 $[0,1)$，在 $t=5$ 时占有 $[1,2)$, 在 $t=10$ 时占有 $[2,3)$，第二个天文学家在 $t=3$ 时占有 $[3,4)$。