Submission #1678051

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <set>

using namespace std;
#define MAXN 100000
#define ll long long
#define rint register int
#define gc() getchar()
inline ll read(ll ans = 0, rint sgn = ' ', rint ch = gc())
{
	for(; ch < '0' || ch > '9'; sgn = ch, ch = gc());
	for(; ch >='0' && ch <='9';(ans*=10)+=ch-'0', ch = gc());
	return sgn-'-'?ans:-ans;
}
int N, Q; ll X[MAXN+5], R[MAXN+5], x; typedef pair<long long,long long> pll; set<pll> S; set<pll>::iterator c; pll d;
int main()
{
	N = read(); X[Q=1] = N; for(int i = read(); i--; X[++Q] = x) for(x = read(); Q && x <= X[Q]; Q--); S.insert(pll(X[Q],1));
	for(ll j, coe1, coe2, mod; (d=*--S.end()).first > X[1]; )
	{
		S.erase(--S.end());
		j = lower_bound(X+1,X+Q+1,d.first)-X-1, coe1 = d.first/X[j]*d.second, coe2 = d.second, mod = d.first%X[j];
		c = lower_bound(S.begin(),S.end(),pll(X[j],0)), c != S.end() && c->first == X[j] ? coe1 += c->second, S.erase(c),0 : 0;
		c = lower_bound(S.begin(),S.end(),pll( mod,0)), c != S.end() && c->first ==  mod ? coe2 += c->second, S.erase(c),0 : 0;
		S.insert(pll(X[j],coe1)), S.insert(pll(mod,coe2));
	}	for(; S.size(); R[S.begin()->first] = S.begin()->second, S.erase(S.begin()));
	for(rint i = N; i; R[i-1] += R[i], i--); for(rint i = 1; i <= N; printf("%lld\n",R[i]), i++); return 0;
}

Submission Info

Judge Result