Submission #848198

---

Source Code Expand

#include <sstream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <string>
#include <cassert>
#include <ctime>
#include <map>
#include <math.h>
#include <cstdio>
#include <set>
#include <deque>
#include <memory.h>
#include <queue>

#pragma comment(linker, "/STACK:64000000")
typedef long long ll;

using namespace std;

const int MAXN = 1 << 18;
const int MOD = 1; // 1000 * 1000 * 1000 + 7;
const int INF = 2e9;
const double PI = acos(-1.0);

int main() {
#ifdef _MSC_VER
	freopen("input.txt", "r", stdin);
#endif

	int n, q;
	while (cin >> n >> q) {
		vector<ll> a(q);
		for (int i = 0; i < q; i++) cin >> a[i];

		vector<ll> old = a;
		vector<ll> b;
		b.push_back(n);
		for (int i = 0; i < q; i++) {
			while (!b.empty() && b.back() >= a[i]) b.pop_back();
			if (b.empty() || a[i] % b.back() != 0) b.push_back(a[i]);
		}
		a = b;

		vector<vector<pair<int, ll> > > e(n);
		for (int i = 1; i < (int)b.size(); i++) {
			ll x = b[i] - b[i - 1];
			while (1) {
				int id = lower_bound(b.begin(), b.begin() + i, x + 1) - b.begin() - 1;
				if (id == -1) break;
				e[id].push_back(make_pair(i, x / b[id]));
				x %= b[id];
			}
		}
		vector<ll> cnt(b.size());
		cnt[(int)b.size() - 1] = old[q - 1] / b.back();
		for (int i = (int)b.size() - 2; i >= 0; i--) {
			cnt[i] = cnt[i + 1];
			for (auto o : e[i]) {
				cnt[i] += cnt[o.first] * o.second;
			}
		}
		
		vector<ll> ans(n);
		for (int i = 1; i < (int)b.size(); i++) {
			ll x = b[i] - b[i - 1];
			while (1) {
				int id = lower_bound(b.begin(), b.begin() + i, x + 1) - b.begin() - 1;
				if (id == -1) {
					if (x) ans[x - 1] += cnt[i];
					break;
				}
				x %= b[id];
			}
		}
		ans[b[0] - 1] += cnt[0];
		
		for (int i = n - 2; i >= 0; i--) {
			ans[i] += ans[i + 1];
		}

		for (int i = 0; i < n; i++) cout << ans[i] << "\n";
		cout << "\n";
	}

	return 0;
}

Submission Info

Judge Result