Blog

题目

Atcoder

思路

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 100010;
int n, m, f[N], d[N];
int q[N], top; 
void work(int x, int y) {
    int t = upper_bound(q + 1, q + top + 1, x) - q - 1;
    if (!t) d[1] += y, d[x + 1] -= y; // 找不到了就差分
    else f[t] += x / q[t] * y, work(x % q[t], y);
}
signed main() {
    cin >> n >> m;
    q[++top] = n; // 防止进行一堆特判
    for (int i = 1, t; i <= m && cin >> t; q[++top] = t, i++)
        while (top && q[top] >= t) top--;
    f[top] = 1; // 一开始的系数是1
    for (int i = top; i >= 2; i--)
        f[i - 1] += q[i] / q[i - 1] * f[i], work(q[i] % q[i - 1], f[i]);
    d[1] += f[1], d[q[1] + 1] -= f[1]; // 特殊处理 第一个询问
    for (int i = 1; i <= n; i++) d[i] += d[i - 1];
    for (int i = 1; i <= n; i++) cout << d[i] << endl;
    return 0;
}