AT2005 [AGC003E] Sequential operations on Sequence

#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
	Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
	Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3)+(x<<1)+(c&15),D);x*=f;}
	Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
	Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x+'0'),0):(write(x/10),pc(x%10+'0'),0);}
	Tp I void writeln(Cn Ty& x){write(x),pc('\n');}
}using namespace FastIO;
Cn int N=1e5+10;
int n,q;LL a[N],f[N],g[N];
I void Sol(LL d,LL w){
	RI j=upper_bound(a+1,a+n+1,d)-a-1;
	if(!j) g[1]+=w,g[d+1]-=w;else f[j]+=d/a[j]*w,Sol(d%a[j],w);
}
int main(){
	RI i,p;LL x;for(read(p,q),a[n=1]=p,i=1;i<=q;i++){read(x);W(n&&a[n]>=x) n--;a[++n]=x;}
	for(f[n]=1,i=n-1;i>=1;i--) f[i]+=a[i+1]/a[i]*f[i+1],Sol(a[i+1]%a[i],f[i+1]);
	for(g[1]+=f[1],g[a[1]+1]-=f[1],i=1;i<=p;i++) writeln(g[i]+=g[i-1]);return 0;
}