记录编号	444657	评测结果	AAAAAAAAAA
题目名称	B先生和天文学家	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2017-09-03 18:05:15	内存使用	4.89 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cassert>
#include<map>
using namespace std;
const int SIZEN=200010;
typedef long long LL;
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
void extend_gcd(LL a,LL b,LL &x,LL &y,LL &d){
	if(b==0){d=a;x=1;y=0;}
	else{extend_gcd(b,a%b,y,x,d);y-=(a/b)*x;}
}
LL inverse(LL a,LL MOD){
	LL x,y,d;
	extend_gcd(a,MOD,x,y,d);
	return (x+MOD)%MOD;
}
LL T,S,n;
LL d[SIZEN]={0};
LL A[SIZEN]={0};
map<LL,vector<int> > M;
LL ans[SIZEN]={0};
LL G,L;//G=gcd(T,S),L=T/G
//there are G rings, each length L
LL S1;//S^-1(mod L)
bool sp_sort(pair<LL,int> a,pair<LL,int> b){
	if(a.first!=b.first) return a.first<b.first;
	return A[a.second]>A[b.second];
}
void calc_ring(vector<int> &ids){
	vector<pair<LL,int> > p;
	for(int i=0;i<ids.size();i++){
		int t=ids[i];
		LL a=A[t]-A[t]%G;
		p.push_back(make_pair(a/G%L*S1%L,t));
	}
	sort(p.begin(),p.end(),sp_sort);
	for(int i=1;i<p.size();i++){
		ans[p[i-1].second] = p[i].first-p[i-1].first;
	}
	ans[p.back().second]=p[0].first+L-p.back().first;
} 
void work(void){
	G=gcd(T,S);//there are total G rings, each length is T/G
	L=T/G;
	S1=inverse(S/G,L);
	for(int i=1;i<=n;i++){
		M[A[i]%G].push_back(i);
	}
	for(map<LL,vector<int> >::iterator key=M.begin();key!=M.end();key++){
		calc_ring(key->second);
	}
	for(int i=1;i<=n;i++) printf("%I64d ",ans[i]);
	printf("\n");
}
void read(void){
	scanf("%I64d%I64d",&T,&n);
	for(int i=1;i<=n;i++){
		scanf("%I64d",&d[i]);
		A[i]=A[i-1]+d[i];
		assert(A[i]>0);
	}
	S=A[n];	
}
int main(){
	freopen("MrBD1.in","r",stdin);
	freopen("MrBD1.out","w",stdout);
	//freopen("D:/MinGWStudio/Templates/DATA/duipai/input.in","r",stdin);
	//freopen("output.out","w",stdout);
	read();
	work();
	return 0;
}