Problem:


モジュロ・クエリ

あなたに N 枚のカードを渡します。どのカードにも一つだけ自然数が書いてあります。ただし、同じ数が書いてあることはありません。

これから質問として、適当な自然数を言います。あなたが持っているカードに書いてある数を私が言った数で割ったときに得られる余りのうち最も大きなものを答えてください。

たとえば、あなたは 3 枚のカードを持っていて、それぞれ 9、3、8 と書いてあるとします。私が「4」と言ったら、9 と 3 と 8 をそれぞれ4 で割った余りを求めてください。余りはそれぞれ 1、3、0 ですが、この中でもっとも大きな余りは3 なので、3 が正しい答えになります。

では始めましょうか。え？ カードがいっぱいあるとたいへんだ？ しょうがないですね。それではコ
ンピュータを使って最大の余りを見つけることにしましょう。カードに書いてある数を、質問された数で割った余りのうち、最大のものを見つけるプログラムを作成してください。なお、質問は１回だけでなく何度もしますが、同じ数を 2 回以上質問することはありません。

入力

入力は１つのデータセットからなる。入力データは以下の形式で与えられる。

N Q
c1 c2 ... cN
q1
q2
:
qQ

１行目にカードの枚数 N (2 ≤ N ≤ 300000) と質問の回数 Q (2 ≤ Q ≤ 100000)  が１つの空白区切りで与えられ、２行目にカードに書かれた数 ci (1 ≤ ci ≤ 300000) が１つの空白区切りで与えられる。続くQ 行に質問として与えられる数 qi (1 ≤ qi ≤ 300000) が与えられる。

出力

質問ごとに最大の余りを１行に出力する。

入力例

3 3
9 3 8
4
6
5

出力例

3
3
4



Sample input:
3 3
9 3 8
4
6
5


Sample output:
3
3
4

Submission status: Wrong Answer

Solution code:
# AOJ 0270: Modular Query
# Python3 2018.6.26 bal4u

N, Q = map(int, input().split())
tbl = [0]*300005
nmax, tbl[0] = 0, 1
c = list(map(int, input().split()))
for k in c:
	tbl[k] = 1
	if k > nmax: nmax = k
	tbl[k & 1] = 1
	tbl[k & 3] = 1
	tbl[k & 7] = 1
for i in range(Q):
	q = int(input())
	if q > nmax: print(nmax)
	else:
		f = 0
		for k in range(q-1, 0, -1):
			for i in range(k, nmax+1, q):
				if tbl[i]:
					print(k)
					f = 1
					break
			if f: break

Submission status: Wrong Answer

Solution code:
n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
p=[0]*(max(c)+1)
for i in c:
	p[i]=1

for k in range(q):
	m=int(raw_input())
	flag=0
	for i in range(m-1,0,-1):
		for pi in p[i::m]:
			if pi:
				print i
				flag=1
				break
		if flag: break

Submission status: Wrong Answer

Solution code:
n,q=map(int,raw_input().split())
c=map(int,raw_input().split())

mxc=max(c)
p=[0]*(mxc+1)
for i in c:
	p[i]=1
	
l=[0]*(mxc+1)
num=0
for i in range(mxc+1):
	l[i]=num
	if p[i]:
		num=1
		
for i in range(q):
	m=int(raw_input())
	sp=mxc
	ans=0
	while 1:
		r=sp%m
		ans=max(ans,r)
		if sp-r==0:break
		sp=l[sp-r]
	print ans

Submission status: Time Limit Exceeded

Solution code:
(N, Q) = map(int, input().split(' '))
card = [int(x) for x in input().split(' ')]
for i in range(0,Q):
	q = int(input())
	print(max([int(x%q) for x in card]))

Submission status: Time Limit Exceeded

Solution code:
(N, Q) = map(int, input().split(' '))
card = [int(x) for x in input().split(' ')]
q = []
for i in range(0,Q):
	q.append(int(input()))
for i in range(0,Q):	
	print(max([int(x%q[i]) for x in card]))

Submission status: Time Limit Exceeded

Solution code:
(N, Q) = map(int, input().split(' '))
card = [int(x) for x in input().split(' ')]
query = []
for i in range(0,Q):
	query.append(int(input()))
for q in query:
	answer = []
	arr = card
	while True:
		n = max(arr)
		p = n%q
		answer.append(p)
		arr = [x for x in arr if x<n-p]
		if not arr:
			print(max(answer))
			break

Submission status: Time Limit Exceeded

Solution code:
(N, Q) = map(int, input().split(' '))
card = [int(x) for x in input().split(' ')]
query = []
for i in range(0,Q):
	query.append(int(input()))
for q in query:
	answer = []
	arr = card
	while arr:
		n = max(arr)
		p = n%q
		answer.append(p)
		arr = [x for x in arr if x<n-p]
	print(max(answer))

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(Q):
    m = -1
    spam = int(input())
    for n in C:
        ham =n%spam 
        m =  max(m,ham) 
    print(m)

Submission status: Time Limit Exceeded

Solution code:
def next_max(lst,mi,v):
    l, r = 0, mi-1
    while l <= r:
        mid = int((l+r)/2)
        if lst[mid] == v: return mid -1
        if lst[mid] > v:
            r = mid - 1
        else:
            l = mid + 1
    return r


N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))
C.sort()
for i in range(Q):
    t = int(input())
    idx = N-1
    m = C[-1]% t
    idx = next_max(C,idx,C[idx]-m)
    while idx >= 0:
        amr = C[idx]%t
        m = max(m,amr) 
        idx = next_max(C,idx,C[idx]-amr)
    print(m)

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))
C.sort()

def next_max(mi,v):
    l, r = 0, mi-1
    while l <= r:
        mid = int((l+r)/2)
        if C[mid] == v: return mid - 1
        if C[mid] > v:
            r = mid - 1
        else:
            l = mid + 1
    return r

for i in range(Q):
    t = int(input())
    idx = N-1
    m = C[-1]% t
    idx = next_max(idx,C[idx]-m)
    while idx >= 0:
        amr = C[idx]%t
        m = max(m,amr) 
        idx = next_max(idx,C[idx]-amr)
    print(m)

Submission status: Time Limit Exceeded

Solution code:
N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))

M = max(C)+1
t1 = [0]*(M)
for v in C:
    t1[v] = 1

t2 = [0]*(M)
v = 0
for i in range(M):
    if t1[i]:
        v = i
    t2[i] = v

for i in range(Q):
    t = int(input())
    n_v = M-1
    m = 0
    while n_v != 0:
        amr = n_v % t
        m = max(m,amr) 
        n_v = t2[n_v-1]

    print(m)

Submission status: Time Limit Exceeded

Solution code:
NQ = raw_input().split()
N = int(NQ[0])
Q = int(NQ[1])

q_list = []

n_list = raw_input().split()

for i in range(Q):
    q_list.append(input())

for i in q_list:
    memo = []
    for j in n_list:
        memo.append(int(j) % i)
    print max(memo)

Submission status: Time Limit Exceeded

Solution code:
# Aizu Problem 0270: Modular Query

import sys, math, os, datetime

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


N, Q = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
for q in range(Q):
    m = int(input())
    print(max([a % m for a in A]))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,raw_input().split())
C=map(int,raw_input().split())
for i in range(Q):
    q=input()
    print max(map(lambda x:x%q,C))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,raw_input().split())
C=set(map(int,raw_input().split()))
for i in range(Q):
    q=input()
    print max(map(lambda x:x%q,C))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, raw_input().split())
c = map(int, raw_input().split())
for i in range(Q):
    q = int(raw_input())
    print max([x % q for x in c])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
for i in range(q):
	m=int(raw_input())
	print max([c[i]%m for i in range(n)])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
p=[0]*(max(c)+1)
for i in c:
	p[i]=1

for k in range(q):
	m=int(raw_input())
	flag=0
	ans=0
	for i in range(m-1,0,-1):
		for pi in p[i::m]:
			if pi:
				ans=i
				break
		if ans>0:
			break
	print ans

Submission status: Accepted

Solution code:
N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))

M = max(C)+1
t1 = [0]*(M)
for v in C:
    t1[v] = 1

t2 = [0]*(M)
v = 0
for i in range(M):
    if t1[i]:
        v = i
    t2[i] = v

for i in range(Q):
    t = int(input())
    n_v = M-1
    m = 0
    while n_v != 0:
        amr = n_v % t
        m = max(m, amr) 
        tmp = n_v-m-1
        if tmp <= 0: break
        n_v = t2[tmp]

    print(m)

Submission status: Accepted

Solution code:
N,Q=map(int,raw_input().split())
c=map(int,raw_input().split())
 
mxc=max(c)
p=[0]*(mxc+1)
for i in c:
    p[i]=1
     
l=[0]*(mxc+1)
num=0
for i in range(mxc+1):
    l[i]=num
    if p[i]:
        num=i
         
for i in range(Q):
    q=int(raw_input())
    sp=mxc
    ans=0
    while 1:
        r=sp%q
        ans=max(ans,r)
        if sp-r<=0:break
        sp=l[sp-r]
    print ans

Submission status: Accepted

Solution code:
# AOJ 0270: Modular Query
# Python3 2018.6.26 bal4u

N, Q = map(int, input().split())
tbl = [0]*300005
nmax, tbl[0] = 0, 1
c = list(map(int, input().split()))
for k in c:
	tbl[k] = 1
	if k > nmax: nmax = k
	tbl[k & 1] = 1
	tbl[k & 3] = 1
	tbl[k & 7] = 1
for i in range(Q):
	q = int(input())
	if q > nmax: print(nmax)
	else:
		f = 0
		for k in range(q-1, -1, -1):
			for i in range(k, nmax+1, q):
				if tbl[i]:
					print(k)
					f = 1
					break
			if f: break

Submission status: Accepted

Solution code:
N,Q=map(int,raw_input().split())
A=map(int,raw_input().split())
maxA=max(A)
T=[0]*(maxA+2)
for i in A:
    T[i]=1
L=[0]*(maxA+2)
num=0
for i in range(maxA+2):
    L[i]=num
    if T[i]==1:
        num=i
for i in range(Q):
    q=input()
    maxv=0
    cur=maxA
    while True:
        p=cur%q
        maxv=max(maxv,p)
        if cur-p<=0: break
        cur=L[cur-p]
    print maxv

Submission status: Accepted

Solution code:
N,Q=map(int,raw_input().split())
c=map(int,raw_input().split())

mxc=max(c)
p=[0]*(mxc+1)
for i in c:
    p[i]=1
    
l=[0]*(mxc+1)
num=0
for i in range(mxc+1):
    l[i]=num
    if p[i]:
        num=i
        
for i in range(Q):
    q=int(raw_input())
    sp=mxc
    ans=0
    while 1:
        r=sp%q
        ans=max(ans,r)
        if sp-r<=0:break
        sp=l[sp-r]
    print ans

Submission status: Accepted

Solution code:
import bisect


n, q = map(int, input().split())
c = list(map(int, input().split()))
c = sorted(c)

for i in range(q):
    query = int(input())
    num = query
    ans = 0
    while True:
        if c[-1] + query < num:
            break
        end = bisect.bisect_left(c, num)
        if end - 1 >= 0:
            ans = max(ans, c[end-1] % query)
        num += query
    print(ans)

Submission status: Accepted

Solution code:
N, Q = list(map(int, input().split()))
C = list(map(int, input().split()))

M = max(C) + 1
T = [0]*(M)
for v in C: T[v] = 1

L = [0]*(M)
m = 0

for i in range(M):
    L[i] = m
    if T[i] : m = i

for i in range(Q):
    q = int(input())
    maxv = 0
    cur = m
    while 0 < cur:
      p = cur % q
      maxv = max(maxv, p)
      if cur - p < 0:  break
      cur = L[cur - p]
    print(maxv)

Submission status: Runtime Error

Solution code:
n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
p=[0]*(max(c)+1)
for i in c:
	p[i]=1

for k in range(q):
	m=int(raw_input())n,q=map(int,raw_input().split())
c=map(int,raw_input().split())
p=[0]*(max(c)+1)
for i in c:
	p[i]=1

for k in range(q):
	m=int(raw_input())
	flag=0
	for i in range(m-1,0,-1):
		for pi in p[i::m]:
			if pi:
				print i
				flag=1
				break
		if flag: break
	else:
		print 0
	flag=0
	for i in range(m-1,0,-1):
		for pi in p[i::m]:
			if pi:
				print i
				flag=1
				break
		if flag: break