题意概括好麻烦，
好吧既然是英文题面那放一下题意。
题意：有 n 个观察员，第一个观察员在 0 秒开始观察星空，随后第i 个观察员会在第 i − 1 个观察员之后 ai 秒观察，第一个观察员也会在第 n 个观察员之后 a1 秒观察。有一颗星星在 [−T, −1] 之间某个整数秒前开始闪烁，之后每隔 T 秒闪烁一次。问每个观察员有多大概率可能成为第一个观察到这颗星星的人。答案乘以 T 输出。
数据范围:1 ≤ T ≤ 109, 2 ≤ n ≤ 2 × 105, 1 ≤ ai ≤ 109
老样子，我们放题目链接
做数学相关题的惯例是列一坨式子然后毫无思路。。。
题目要求第一个观察到，我们就先考虑怎样能观察到。令观察员i第一次观察的时刻为si，星星第一次出现的时刻为x，令S=∑ai ， 绕完一圈后，(x+=S)%=T 。那么，i观察到星星仅当 si≡x(mod T)。我们将si对T取模，那么，仅当si=x时i能观察到星星。
考虑x的变化过程： (x+=S)%=T。令g=(S,T)，则x->x`满足 g|(x-x`)，即，x在变化过程中一定依次经过了和它同余的所有值，然后循坏（如 S=3,T=7,则有 0->3->6->2->5->1->4->0->...）。
因此，我们可以把对g同余的si单独拎出来当一组，这样就可看作S`(S/g)和T`(T/g)互质。对于每组，不同的si一定在环上有一个绝对的相对位置（以上述例子为例,s={4,1,3}，那么相对位置为 3->1->4->3->...）。那么，相邻两个位置之间的长度差即为答案（以上述例子为例，si=4,答案为1->4的长度差1，si=1,答案为3->1的长度差4，si=3,答案为4->3的长度差2）。也就是说，只要求出他们的相对位置差，我们就得到了答案。（你问为什么间隔就是答案？可以想象一下每次选择这个x循环变化的环上一点往后跳，跳到有si=x的x就结束了）
我们不妨假定x初始值为0,x变化了k次（即走了k圈）成为了si（注意，所有si是对T取模的）。则有si=k*S`(mod T`)。于是我们就可以对于每个si用exgcd在O(log)时间内求出k。我们把同环内的k从小到大排个序，k[i]-k[i-1]就是拥有k[i]的观察员的答案。总时间复杂度O(nlog)。
//实际上，可以发现并不需要每次都用exgcd求k。我们可以求出S'*-xx=1(mod T')中的xx,每次xx*si就得到k了。因此nlogn的logn是排序带的，所以跑得还蛮快，没有IO优化也只要150ms，看了看大部分做法要300+ms 。
#include <bits/stdc++.h>
using namespace std; #define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i) typedef long long ll; const int N=2e5+; ll S,T,g; void gcd(ll a,ll b,ll &x,ll &y){
if(b==){
g=a;
x=;
y=;
return ;
}
gcd(b,a%b,y,x);
y-=x*(a/b);
x%=T;y%=T;
} int n,s[N];
ll ans[N],xx,yy; struct Node{
int no;
ll r,val,k;//第k圈
}a[N]; bool cmp(Node aa,Node bb){
if(aa.r!=bb.r) return aa.r<bb.r;
if(aa.k!=bb.k) return aa.k<bb.k;
return aa.no<bb.no;
} int main(){
scanf("%lld%d",&T,&n);
rep(i,,n) scanf("%d",&s[i]); rep(i,,n) a[i].val=(a[i-].val+s[i])%T; S=(a[n].val+s[])%T;
gcd(S,T,xx,yy);
S/=g;T/=g;
xx*=-;xx=(xx%T+T)%T; rep(i,,n){
a[i].no=i;
a[i].r=a[i].val%g;
a[i].val/=g;
a[i].k=a[i].val*xx%T;
} sort(a+,a++n,cmp);
int L=;a[n+].r=-;
rep(i,,n)
if(a[i].r!=a[i+].r){
rep(j,L+,i) ans[a[j].no]=a[j].k-a[j-].k;
ans[a[L].no]=a[L].k-a[i].k+T; L=i+;
} rep(i,,n) printf("%lld ",ans[i]); return ;
}