Submission #1838138

---

Source Code Expand

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N=100010;

int n,q,t;
ll b[N],Q[N],a[N],c[N];

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}

inline void read(int &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline void read(ll &x){
  char c=nc(); x=0;
  for(;c>'9'||c<'0';c=nc());for(;c>='0'&&c<='9';x=x*10+c-'0',c=nc());
}

inline void work(ll x,ll y){
  int p=upper_bound(Q,Q+1+t,x)-Q-1;
  if(!p) a[1]+=y,a[x+1]-=y;
  else c[p]+=y*(x/Q[p]),work(x%Q[p],y);
}

int main(){
  read(n); read(q);
  if(q==1){
    for(int i=1;i<=n;i++) printf("%d\n",1); return 0;
  }
  for(int i=1;i<=q;i++) read(b[i]);
  Q[++t]=b[q];
  for(int i=q-1;i;i--){
    if(b[i]>=Q[t]) continue;
    Q[++t]=b[i];
  }
  if(n<Q[t]) Q[++t]=n; reverse(Q+1,Q+1+t);
  c[t]=1;
  for(int i=t;i>1;i--)
    c[i-1]+=c[i]*(Q[i]/Q[i-1]),work(Q[i]%Q[i-1],c[i]);
  for(int i=1;i<=n;i++) a[i]+=a[i-1];
  for(int i=1;i<=Q[1];i++) a[i]+=c[1];
  for(int i=1;i<=n;i++) printf("%lld\n",a[i]);
  return 0;
}

Submission Info

Judge Result