Problem:


Score : 1400 points

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.

Constraints

1 ≦ N ≦ 10^5

0 ≦ Q ≦ 10^5

1 ≦ q_i ≦ 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.

Sample Input 1

5 3
6
4
11

Sample Output 1

3
3
3
2
0

After the first operation, the sequence becomes: 1,2,3,4,5,1.

After the second operation, the sequence becomes: 1,2,3,4.

After the third operation, the sequence becomes: 1,2,3,4,1,2,3,4,1,2,3.

In this sequence, integers 1,2,3,4,5 appear 3,3,3,2,0 times, respectively.

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



Sample input:
5 3
6
4
11


Sample output:
3
3
3
2
0

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

###########

n,q=ii()
a=[0]*q
for j in range(q):
    a[j]=long(raw_input())
x=[1]*a[q-1]
a.pop()
for qr in reversed([n]+a):
    y=[0]*qr
    for j in range(len(x)/qr):
        for k in range(qr):
            y[k] += x[j*qr+k]
    for k in range(len(x)%qr):
        y[k] += x[(len(x)/qr)*qr+k]
    x=[y[i] for i in range(len(y))]

for i in x:
    print i

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

###########

n,q=ii()
a=[0]*q
for j in range(q):
    a[j]=i()
x=[1]*a[q-1]
a.pop()
for qr in reversed([n]+a):
    y=[0]*qr
    for j in range(len(x)/qr):
        for k in range(qr):
            y[k] += x[j*qr+k]
    for k in range(len(x)%qr):
        y[k] += x[(len(x)/qr)*qr+k]
    x=[y[i] for i in range(len(y))]

for i in x:
    print i

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,raw_input().split( ))
L = range(1,N+1)
K = range(1,N+1)
QL = []
for i in range(Q):
    IN = input()
    QL.append(IN)

for i in range(Q):
    if len(L) < QL[i]:
        t = QL[i]%len(L)
        L = L*(QL[i]/len(L))
        for k in range(t):
            L.append(L[k])
    elif len(L) > QL[i]:
        L = L[0:QL[i]]

nums ={}
for num in map(str,L):
    nums[num] = nums.get(num,0)+1

for k in range(1,N+1):
    if str(k) in nums:
        print nums[str(k)]
    else:
        print '0'

Submission status: Accepted

Solution code:
import bisect,sys

input=sys.stdin.readline

N,Q=map(int,input().split())
que=[(N,0)]
for i in range(Q):
    q=int(input())
    que.append((q,i+1))

que.sort(reverse=True)

ext=[]
while que:
    q,id=que.pop()
    if not ext:
        ext.append((q,id))
    else:
        if ext[-1][1]<id:
            if ext[-1][0]==q:
                ext.pop()
            ext.append((q,id))

Q=len(ext)
data=[1]*Q
data[0]=ext[0][0]
edge=[[] for i in range(Q)]
nowext=[ext[0][0]]
for i in range(1,Q):
    q=ext[i][0]
    rest=q
    while True:
        id=bisect.bisect_right(nowext,rest)
        if id==0:
            break
        else:
            edge[id-1].append((i,rest//nowext[id-1]))
            rest%=nowext[id-1]
    nowext.append(ext[i][0])
    data[i]=rest

#print(edge)

dp=[1]*Q
for i in range(Q-2,-1,-1):
    temp=0
    for nv,c in edge[i]:
        temp+=dp[nv]*c
    dp[i]=temp

#print(dp)
#print(data)

minus=[0]*(ext[0][0]+1)
for i in range(Q):
    minus[data[i]]+=dp[i]

base=sum(dp)
for i in range(1,N+1):
    if i-1<=ext[0][0]:
        base-=minus[i-1]
    print(base)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from heapq import heappop, heappush

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def choose_increasing(q):
    A = []
    for x in q:
        while A and A[-1] >= x:
            A.pop()
        A.append(x)
    return np.array(A, np.int64)

def main(A, N):
    heap = [(-A[-1], 1)]
    for n in A[::-1]:
        while True:
            if -heap[0][0] <= n:
                break
            x, coef = heappop(heap)
            while heap and heap[0][0] == x:
                _, c = heappop(heap)
                coef += c
            q, r = divmod(-x, n)
            heappush(heap, (-n, coef * q))
            heappush(heap, (-r, coef))
    ret = np.zeros(N + 10, np.int64)
    for x, c in heap:
        x = -x
        ret[1] += c
        ret[x + 1] -= c
    ret = np.cumsum(ret)
    return ret[1:N + 1]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:], i8))
    cc.compile()

from my_module import main

N, Q = map(int, readline().split())
q = [N] + list(map(int, read().split()))

A = choose_increasing(q)
ans = main(A, N)
print('\n'.join(map(str, ans.tolist())))

Submission status: Runtime Error

Solution code:
	if self.buffInGod > 0 then
		if real == 2 or real == 3 then
			g_mvcNotify:notifyToRootView("playEffect", self.posXY,
				'00buff/wudi.json',self.posZ,0,self.faceTo,'effect1')
		end
		return false
	end

Submission status: Runtime Error

Solution code:
function SignetBackpacker:refreshBag()
	g_asyncLoad:overFor(self)

	if self.signetTal[self.listSlotID] then
		return
	end

Submission status: Runtime Error

Solution code:
function SignetBackpacker:refreshBagData(data)
	if data then
		self.originData = data
	end
	self.signetTal = {}
	self:refreshBag()
end

Submission status: Runtime Error

Solution code:
	if attackObj and (real == 1 or real == 3) then
		if not args or args.from ~= 9 then	-- 9表示来自反弹的
			local nowRound = self._scene.nowRound
			attackObj.roundRecordTb[nowRound] = attackObj.roundRecordTb[nowRound] or {}
			local recordTb = attackObj.roundRecordTb[nowRound]
			local tdmg1 = recordTb["roundTotalDmg"] or 0
			recordTb["roundTotalDmg"] = tdmg1 + damage
			if not args or args.from ~= "buff" then		-- 非buff的伤害来源
				local tdmg2 = recordTb["roundTotalDmgNoBuff"] or 0
				recordTb["roundTotalDmgNoBuff"] = tdmg2 + damage
			end
		end
	end

Submission status: Runtime Error

Solution code:
type Container struct {
	services sync.Map //map[string]IService
	remotes  map[string]bool
	factory  IFactory

	nsq       *nsq.NSQRPCServer
	nsqClient *nsq.NSQRPCClient

	option ContainerOption
	inited bool
}