Submission #1842250

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;
ll v[MAXN] , ans[MAXN] , has[MAXN];
int sum = 1 , q , n;
int main(){
    cin >> n >> q;
    v[1] = n;
    for(int i = 1 ; i <= q ; ++ i){
        ll x;
        cin >> x;
        while(sum && x < v[sum])
        	sum --;
        v[++ sum] = x;
    }
    has[sum] = 1;
    for(int i = sum ; i >= 1 ; -- i){
    	if(has[i] == 0) continue;
    	ll now = v[i];
    	int last = i;
    	while(true){
			int ll = 0 , rr = last - 1;
			while(ll < rr){
				int mid = (ll + rr + 1) >> 1;
				if(now >= v[mid])
					ll = mid;
				else
					rr = mid - 1;
			}
			if(ll == 0){
				ans[now] += has[i];
				break;
			}
			else{
				has[ll] += now / v[ll] * has[i];
				now %= v[ll];
				last = ll;
			}	
		}
    }
    for(int i = n ; i >= 1 ; -- i)
    	ans[i - 1] += ans[i];
    for(int i = 1 ; i <= n ; ++ i)
    	cout << ans[i] << endl;
    return 0;
}

Submission Info

Judge Result