Submission #1774086

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

typedef long long s64;

inline s64 getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	s64 res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 100000;

int n, m;

int sta_n;
s64 sta[MaxN + 2];

s64 occur[MaxN + 2];
s64 sum[MaxN + 2];

inline int jump(s64 x, int r)
{
	int l = 1;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (sta[mid] > x)
			r = mid - 1;
		else
			l = mid + 1;
	}
	return r;
}

int main()
{
	cin >> n >> m;

	sta[sta_n = 1] = n;
	for (int i = 1; i <= m; ++i)
	{
		s64 l = getint();
		while (sta_n && l <= sta[sta_n])
			--sta_n;
		sta[++sta_n] = l;
	}

	occur[sta_n] = 1;
	for (int i = sta_n; i; --i)
	{
		s64 l = sta[i];
		int k = jump(l, i - 1);

		while (k > 0)
		{
			occur[k] += l / sta[k] * occur[i];
			k = jump(l %= sta[k], k - 1);
		}

		sum[1] += occur[i];
		sum[l + 1] -= occur[i];
	}

	s64 cur = 0;
	for (int i = 1; i <= n; ++i)
		printf("%lld\n", cur += sum[i]);

	return 0;
}

Submission Info

Judge Result