Submission #847459

---

Source Code Expand

//In the name of Allah
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1000 * 100 + 100; 
typedef long long ll; 


ll a[maxN]; 
ll z[maxN]; 
ll pref[maxN];
ll ans[maxN]; 


int main() {
	ios::sync_with_stdio(false); cin.tie(0); 
	int n,q; cin >> n >> q; 
	a[0] = n; 
	int en = 1; 
	for( int i = 0 ; i < q ; i++ ) { 
		ll x; cin >> x; 
		while( en > 0 && a[en-1] >= x ) 
			en--; 
		a[en++] = x; 
	}

	q = en; 
	z[q-1] = 1; 
	for( int i = q - 1 ; i > 0 ; i-- ) { 
		ll d = a[i] / a[i-1]; 
		z[i-1] += d * z[i]; 
		ll rem = a[i] % a[i-1]; 
		while( rem > a[0] ) { 
			int ind = upper_bound( a , a + i , rem ) - a - 1; 
			z[ind] += rem / a[ind] * z[i]; 
			rem = rem % a[ind];
			//cerr << "H "  << rem << endl;
		}
		//cerr << " ! "  << rem << endl;
		pref[rem]+= z[i]; 
	}
	for( int i = n - 1 ; i >= 0 ; i-- ) { 
		pref[i] += pref[i+1]; 
		ans[i] = pref[i+1] + z[0]; 
		if( i >= a[0] ) ans[i] = 0;
	}
	for( int i = 0 ; i < n ; i++ ) 
		cout << ans[i] << '\n'; 
}

Submission Info

Judge Result