# [AGC003]E - Sequential operations on Sequence

2018/01/26 21:45

Time limit : 2sec / Memory limit : 256MB

## Problem Statement

Snuke got an integer sequence from his mother, as a birthday present. The sequence has $N$ elements, and the $i$-th of them is $i$. Snuke performs the following $Q$ operations on this sequence. The $i$-th operation, described by a parameter $q_i$, is as follows:

• Take the first $q_i$ elements from the sequence obtained by concatenating infinitely many copy of the current sequence, then replace the current sequence with those $q_i$ elements.

After these $Q$ operations, find how many times each of the integers $1$ through $N$ appears in the final sequence.

<!--more-->

## Constraints

• $1≦N≦10^5$
• $0≦Q≦10^5$
• $1≦qi≦10^18$

All input values are integers.

## Input

The input is given from Standard Input in the following format:

$N;Q$ $q_1$ $...$ $q_Q$

## Output

Print N lines. The i-th line (1≦$i$≦$N$) should contain the number of times integer $i$ appears in the final sequence after the $Q$ operations.

5 3 6 4 11

3 3 3 2 0

## Sample Input 2

10 10 9 13 18 8 10 10 9 19 22 27

## Sample Output 2

7 4 4 3 3 2 2 2 0 0

# CODE

ps:中途变量混乱，n m num难以分清

#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int n,num,m;
ll a[101010];
ll f[101010],s[101010];
void sol(ll x,ll doe)
{
if (x<a[1])
{
s[x]+=doe;
return;
}
int l=1,r=n;
int y;
while (l<=r)
{
int mid=(l+r)/2;
if (a[mid]<=x)
{
y=mid;
l=mid+1;
}
else r=mid-1;
}
f[y]+=doe*(x/a[y]);
x=x%a[y];
if (x) sol(x,doe);
}
int main()
{
//	freopen("E.in","r",stdin);
//	freopen("E.out","w",stdout);
scanf("%d%d",&n,&m);
num=1;
a[1]=n;
ll x;
for (int i=1;i<=m;++i)
{
scanf("%lld",&x);
while (x<=a[num] && num)
--num;
++num;
a[num]=x;
}
m=n;
n=num;
f[n]=1;
for (int i=n-1;i>=1;--i)
{
f[i]+=f[i+1]*(a[i+1]/a[i]);
sol(a[i+1]%a[i],f[i+1]);
}
for (int i=a[1];i>=1;--i)
s[i]+=s[i+1];
for (int i=1;i<=a[1];++i)
s[i]+=f[1];
for (int i=1;i<=m;++i)
printf("%lld\n",s[i]);
return 0;
}


0
0 收藏

0 评论
0 收藏
0