Problem:


Score : 400 points

Problem Statement

Given is a number sequence A of length N.

Find the number of integers i \left(1 \leq i \leq N\right) with the following property:

For every integer j \left(1 \leq j \leq N\right) such that i \neq j , A_j does not divide A_i.

Constraints

All values in input are integers.

1 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^6

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answer.

Sample Input 1

5
24 11 8 3 16

Sample Output 1

3

The integers with the property are 2, 3, and 4.

Sample Input 2

4
5 5 5 5

Sample Output 2

0

Note that there can be multiple equal numbers.

Sample Input 3

10
33 18 45 28 8 19 89 86 2 4

Sample Output 3

5



Sample input:
5
24 11 8 3 16


Sample output:
3

Submission status: Wrong Answer

Solution code:
import heapq as hp
n = int(input())
a = list(map(int, input().split()))
hp.heapify(a)
ans = 0
while len(a) > 0:
    b = a[0]
    if b in a:
         ans += -1
    a = [i for i in a if i % b != 0]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
L=list(map(int,input().split()))
a=0
b=N
if 1 in L:
  print(0)
else:
  set(L)
  for i in L:
    for j in L:
      if i!=j and i%j==0:
        a+=1
        if a>=1:
          b=b-1
  print(b)

Submission status: Wrong Answer

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    # print (A)
    ans = 0
    for i in range(N - 1, -1, -1):
        a = A[i]
        flag = True
        if i + 1 < N and A[i] == A[i + 1]:
            flag = False
        else:
            for j in range(i):
                if a % A[j] == 0:
                    flag = False
                    break
                if A[j] * 2 > a:
                    break

        if flag:
            ans += 1

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from math import sqrt

N = int(input())
A = list(map(int, input().split()))
A.sort()
#print(A)
ans = []
res = []
nans = 0
doubling = 0
i = 0
while i < N:
  a = A[i]
  sqa = sqrt(a)
  #print(i,a)
  if i == 0:
    flag = False
    while i + 1 < N:
      bufa = A[i+1]
      if bufa == a:
        i += 1
        flag = True
      else:
        break
    if flag:
      nans += 1
      doubling += 1
      ans.append(a)
    else:
      nans += 1
      ans.append(a)
      res.append(a)
  elif i < N-1:
    flag = False
    while i + 1 < N:
      bufa = A[i+1]
      if bufa == a:
        i += 1
        flag = True
      else:
        break
    if flag:
      d = 0
      flag2 = True
      while ans[d]<=sqa:
        if a%ans[d] == 0:
          flag2 = False
          break
        if nans -1 == d:
          break
        d += 1
      if flag2:
        nans += 1
        doubling += 1
        ans.append(a)
    else:
      d = 0
      flag2 = True
      while ans[d]<=sqa:
        if a%ans[d] == 0:
          flag2 = False
          break
        if nans -1 == d:
          break
        d += 1
      if flag2:
        nans += 1
        ans.append(a)
        res.append(a)
  else:
    d = 0
    flag2 = True
    while ans[d]<=sqa:
      if a%ans[d] == 0:
        flag2 = False
        break
      if nans -1 == d:
        break
      d += 1
    if flag2:
      nans += 1
      ans.append(a)
      res.append(a)
  i += 1
        
        
print(len(res))

Submission status: Wrong Answer

Solution code:
n = int(input())
c = set(map(int,input().split()))
a = list(c)
a.sort()
b = []
flag = 0
for i in range(len(a)):
    for j in range(len(b)):
        if a[i]%b[j] == 0:
            flag = 1
            break
    if flag == 0:
        b.append(a[i])
    flag = 0
ans = len(b)
if ans == 1:
    print(0)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int,input().split()))
c = 0
for i in range(N):
  d =0 #カウンタの初期化
  for j in range(N):
    if a[i] % a[j] == 0:
      c = c+1
      break
print(N-c)

Submission status: Wrong Answer

Solution code:
from collections import deque

N = int(input())
A = list(map(int,input().split()))

A.sort()
d = deque()
for i in range(N-1):
    if A[i] != A[i+1]:
        d.append(A[i])
if A[N-1] != A[N-2]:
    d.append(A[N-1])

ans_que = deque()
ban = dict()
border = pow(10, 6)
while len(d):
    num = d.popleft()
    if ban.get(num) != 1:
        ans_que.append(num)
        ban_num = num
        while ban_num <= border:
            ban[ban_num] = 1
            ban_num += num

print(len(ans_que))

Submission status: Wrong Answer

Solution code:
# Problem D - Not Divisible

# input
N = int(input())
a_nums = list(map(int, input().split()))
a_nums = sorted(a_nums)

# initialization
fact_nums = {}
pattern = []
left = 0
right = N+1

# binary search
while abs(right-left)>1:
    mid = (right + left) // 2
    is_success = False

    # check
    tmp_count = 0
    for i in range(N):
        is_ok = True
        for j in range(i):
            if i==j:
                continue
            if a_nums[i]%a_nums[j]==0:
                is_ok = False
                break
        if is_ok:
            tmp_count += 1
            if tmp_count>=mid:
                is_success = True
                break

    if is_success:
        left = mid
    else:
        right = mid

if len(list(set(a_nums)))==1:
    left = 0

# output
print(left)

Submission status: Wrong Answer

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7


def get_divisors(n):
    divs = []
    for i in range(2, int(n**0.5)+1):
        c = 0
        while n % i == 0:
            n = n // i
            c += 1
        if c > 0:
            divs.append((i, c))
    if n > 1:
        divs.append((n, 1))
    return divs

N = ri()
A = rl()

import collections

cnt = collections.Counter(A)
A = []
for k, v in cnt.items():
	if v > 1: continue
	A.append(k)
N = len(A)

A.sort()

H = collections.defaultdict(set)
D = []
for i, a in enumerate(A):
	divs = get_divisors(a)
	D.append(divs)
	for d, c in divs:
		for j in range(1, c+1):
			k = pow(d, j)
			H[k].add(i)

del_list = set()
Ns = range(N)
for i, divs in enumerate(D):
	if i in del_list: continue
	s = set(Ns)
	for d, c in divs:
		for j in range(1, c+1):
			k = pow(d, j)
			s &= H[k]
	del_list |= s - set([i])
print(N-len(del_list))

Submission status: Wrong Answer

Solution code:
N=int(input())
List=[int(i) for i in input().split()]
list.sort(List,reverse=True)
p=0
for i in range(0,N-1):
    j=i+1
    while(List[i]%List[j]!=0 and j<N-1):
        j+=1
    if j==N-1:
        if List[i]%List[j]!=0:
             p+=1
if List[N-2]!=List[N-1]:
    print(p+1)
else:
    print(p)

Submission status: Wrong Answer

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

res = 0
count = 0
dividelist = listA
for i, Ai in enumerate(listA[:]):
    for j, Aj in enumerate(dividelist):
        if i == j+count:
            continue
        if Ai % Aj == 0:
            res += 1
            count += 1
            dividelist.remove(Ai)
            break

print(N - res)

Submission status: Wrong Answer

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

A.sort()

i=0
flag=0
while i<len(A):
    t = A[i]
    A1 = A[0:i+1]
    A2 = []
    for n in A[i+1:N]:
        if n % t != 0:
            A2.append(n)
        if n == t:
            flag = 1
    if flag == 1:
        del A1[-1]
    A1.extend(A2)
    A = A1
    i += 1

print(len(A))

Submission status: Wrong Answer

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split()))
A.sort()
ans=0
b=[A[0]]
for i in range(1,N):
    flag=0
    a=A[i]
    r=bisect.bisect_right(b,a//2)
    for j in range(r):
        if a%b[j]==0:
            flag=1
            break
    if flag==0:
        b.append(a)
if len(b)==1 and N>1:
    print(0)
else:
    print(len(b))

Submission status: Wrong Answer

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

setA = set(A)
result = 0

if N == 1:
    print(0)
else:
    for i in range(N):
        tmp = A[i]
        A[i] = 0
        setA = set(A)
        A[i] = tmp
        if 1 in setA:
            continue

        for a in setA:
            if a == 0:
                continue
            if A[i] % a == 0:
                break
        else:
            result += 1

    print(result)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import time


s = time.time()
def make_divisors_exist(n):
    #divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            if exists[i]:
                if i != n:
                    return True
            #divisors.append(i)
            i2 = n // i
            if i != i2: # choufuku
                if exists[i2]:
                    if i2 != n:
                        return True
                #divisors.append(i2)

    # divisors.sort()
    #return divisors
    return False



input = raw_input
input()
As_0 = map(int, input().split(" "))

out = 0

counter = Counter(As_0)
As = counter.keys()

max_A = max(As)
exists = [False] * (max_A + 1)

timeover = False
for A in As:
    exists[A] = True

s = time.time()
for A1, num in counter.items():
    e = time.time()
    tdiff = e-s

    if tdiff >= 1.8:
        #print(tdiff)
        break

    if num >= 2:
        continue
    
    exist = make_divisors_exist(A1)

    if not exist:
        out += 1

print(out)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
A.sort()
D=defaultdict(int)
for some in A:
    D[some]+=1

ans = 0
for i in range(N):
    if D[A[i]] == 1:
        flag=True
        for j in range(i):
            if A[i] % A[j] == 0:
                flag = False 
                break
            if A[j]**2 > A[i]:
                break
        if flag:
            ans += 1
    else:
        pass
    
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n = int(input())
an = list(map(int, input().split()))

an.sort()
an = deque(an)
ls = deque()
same = -1
while an:
    a = an.popleft()
    t = True
    if same == a:
      continue
    for i in ls:
        if i > a ** (1/2):
            t = False
            break
        if a == i:
            ls.pop()
            same = a
            t = False
            break
        if a % i == 0:
            t = False
            break
    if t:
        ls.append(a)

print(len(ls))

Submission status: Wrong Answer

Solution code:
n = int(input())
A = list(map(int,input().split()))
A.sort()
table = [A.count(i) for i in range(A[-1]+1)]
A = list(set(A))
A.sort()
ans = []
if len(A) == 1:
    print(0)
elif A[0] == 1:
    print(1)
else:
    is_prime = [False] * (A[-1]+1)
    for a in A:
        if table[a] == 1:
            is_prime[a] = True
    for i in A:
        if not is_prime[i]:
            continue
        for j in range(i * 2, A[-1]+1, i):
            is_prime[j] = False
    ans = [i for i in range(A[-1]+1) if is_prime[i]]
    print(len(ans))

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))

a.sort()
tf = [False] * (10 ** 6 + 1)
ans = 0
for i in range(n):
    cnt = a[i]
    cc = 1
    if i != n -1:
        ll = i + 1
    else:
        ll = i - 1
    if not tf[cnt] and a[i] != a[ll]:
        ans += 1
        while cnt * cc <= max(a):
            tf[cnt * cc] = True
            cc += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

l = [int(x) for x in input().split()]
mp = [1]*n


for i in range(n):
    for j in range(i+1,n):
        if(mp[j]==0):
            continue
        if(l[j]==l[i]):
            mp[i] = 0
            mp[j] = 0
            continue
        if(l[j]%l[i]==0):
            mp[j] = 0
            continue

print(sum(mp))

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
a.sort()
k = len(a)
ok = [0] * k
for i in range(k):
    if ok[i] == 1:
        continue
    if i < k - 1 and a[i] == a[i + 1]:
        ok[i] = 1
    if a[i] < 2 * 10:
        for j in range(i + 1, k):
            if a[j] % a[i] == 0:
                ok[j] = 1
    else:
        times = 1
        while a[i] * times < a[-1]:
            r = bisect.bisect_left(a, a[i] * times)
            l = bisect.bisect_left(a, a[i] * times)
            if r != l:
                for idx in range(l, r):
                    ok[idx] = 1
            times += 1
print(len([i for i in ok if i == 0]))
# print(ok) WAはどこ？

Submission status: Wrong Answer

Solution code:
import sys
N = list(map(int, input().split()))
A= list(map(int, input().split()))
B=sorted(list(set(A)),reverse=True)
count=0
# if len(A)==1:
#     print('0')
#     sys.exit()
count=len(B)-len(A)

for n in range(len(B)):
    judge=0
    for j in range(n+1,len(B)):
        if n!=j and B[n]%B[j]==0:
            judge=1
            break

    if judge==0:
        count+=1
if count<0:
    print('0')
    sys.exit()
print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = sorted(list(map(int, input().split())))
ans = 0
chk = 0
while len(a) > 0:
    if len(a) == 1:
        ans += 1
        break
    a0 = a[0]
    if a0 in a[1:-1]:
        ans -= 1
    l = [i for i in a if i%a0 != 0]
    ans += 1
    a = l

print(ans)

Submission status: Wrong Answer

Solution code:
input()
A = sorted(map(int, input().split()))
k = len(list(x for x in set(A) if A.count(x) > 1))

B = 0
while True:
    p = A[0]
    B += 1
    A = [e for e in A[1:] if e % p !=0]
    if not A:
        break
print(B-k)

Submission status: Wrong Answer

Solution code:
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            yield i
            if i != n // i:
                yield n//i
        i += 1

n,*A = get_all_int()
A.sort()



C = dict(Counter(A))
keys = C.keys()
# log(C)

B = []
for i,a in enumerate(A):
    if C[a] == 1:
        B.append(a)

ans = 0

checks = [False] * (1000009)

for i,a in enumerate(B):
    if not checks[a]:
        ans += 1
        for j in range(a, 1000009, a):
            checks[j] = True

print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
li2 = li[:]
li2.sort(reverse=True)
ans = 0

if len(set(li)) == 1:
    ans = 0
else:
    for i,num in enumerate(li2,1):
        temp = 0
        j_list = li2[i:]
        for j in j_list:
            if num % j == 0:
                break
            else:
                temp += 1
        if temp == n - i and n != i:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(set(map(int, input().split())))
A.sort()
s = set()
ans = N

if len(A)==1:
    print(0)
else:
    for i, b in enumerate(A):
        if i==0:
            s.add(b)
            continue
        else:
            buf = b
            t = 1
            for j in range(2, int(b**0.5)+1):
                while b%j==0:
                    b //= j
                    t *= j
                    if t in s:
                        ans -= 1
                        break
                if not b:
                    break
            s.add(buf)

    print(ans)

Submission status: Wrong Answer

Solution code:
l = int(input())
n = [int(i) for i in input().split()]
u = n.copy()

n.sort()
u.sort(reverse=True)

counter = 0

for i in range(l):
  if n.count(n[i]) >= 2:
      counter += 1
      break
  else:
    for j in range(l):
      if u[i] == n[j]:
        pass
      elif u[i] % n[j] == 0:
        counter += 1
        break
      else:
        pass

print(l - counter)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = a

s = 0
for i in a:
  t = 0
  for j in b:
    if i%j == 0 and j != i:
      t += 1
  if t == 0:
    s += 1
print(s)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = [True] * len(A)


A.sort()

for i in range(len(A)):
        if A[i] > 1010:
                break
        for j in range(i-1, len(A)):
                if i - 1 < 0:
                        continue
                if i == j:
                        continue
                if A[j] < A[i]:
                        continue
                if ans[j]:
                        if A[j] % A[i] == 0:
                                ans[j] = False


count = 0
for i in ans:
        if i:
                count += 1
print(count)

Submission status: Wrong Answer

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

A.sort(reverse=True)
S=0
b=4
if len(set(A)) == 1:
        print(0)

else:
    for i in range(N):
        for j in range(i+1,N):
            if A[i]%A[j]==0:
                break
            if j==4:
                S += 1
    print(int(S+1))