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:
n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=True)
count=0
for i in range(n-1):
    k=(i+n)//2
    if a[i]%a[k]==0:
        continue
    elif a[i]//2<a[k]:
        for j in range(k+1,n):
            if a[i]%a[j]==0:
                break
        else:
            count+=1
    elif a[i]//2>a[k]:
        for j in range(i+1,n):
            if a[i]%a[j]==0:
                break
        else:
            count+=1
if a[n-1]==a[n-2]:
    print(count)
else:
    print(count+1)

Submission status: Wrong Answer

Solution code:
_ = int(input())
a = [int(i) for i in input().split()]

ans = 0
a_sort = sorted(a)
div = []
dup = 0
dup_list = [0 for i in range(1000010)]

for i in a_sort:
	dup_list[i] += 1

for i in dup_list:
	if i > 1:
		dup += 1


for i, n in enumerate(a_sort):
	for x in div:
		if n == x:
			break
		if n%x == 0:
			break
	else:
		ans += 1
		div.append(n)

print(ans-dup)

Submission status: Wrong Answer

Solution code:
"""
    こんにちは。これはクシャルです
    
    Author : thekushalghosh (クシャル)
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time
start_time = time.time()
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
def qw(arr,n):
    s = dict()
    c = 0
    max_ele = -10**9
    for i in range(n):  
        s[arr[i]] = 1 
        max_ele = max(max_ele, arr[i])
    res = dict() 
    for i in range(n):  
        if (arr[i] != 0): 
            for j in range(arr[i] * 2,max_ele + 1, arr[i]):
                if (j in s.keys()): 
                    res[j] = 1
    for x in res: 
        c = c + 1
    return(c)
def solve():
    n = inp()
    a = inlt()
    q = counter(a)
    print(len(list(set(a))) - qw(list(set(a)),len(list(set(a)))) - len(q) + q.count(0) + q.count(1))
            
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
 
def main():
    global tt
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
        sys.stdout.close()
    
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
 
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * (max(a) + 1)
    for i in range(len(a)):
        q[a[i]] = q[a[i]] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)

def power_two(n):
    if n == 1:
        return(True)
    sttr = str(n)
    len_str = len(sttr)
    sttr = list(sttr)
    num = 0
    if (len_str == 1 and sttr[len_str - 1] == '1'): 
        return(False)
    while (len_str != 1 or sttr[len_str - 1] != '1'):
        if ((ord(sttr[len_str - 1]) - ord('0')) % 2 == 1):
            return(False)
        j = 0; 
        for i in range(len_str):  
            num = num * 10 + (ord(sttr[i]) - ord('0')); 
            if (num < 2): 
                if (i != 0):  
                    sttr[j] = '0'
                    j += 1
                continue
  
            sttr[j] = chr((num // 2) + ord('0'))
            j += 1; 
            num = (num) - (num // 2) * 2
        len_str = j
    return(True)

def getLeftmostBit(n): 
    m = 0
    while (n > 1) : 
        n = n >> 1
        m += 1
    return(m)
def getNextLeftmostBit(n, m) : 
    temp = 1 << m 
    while (n < temp) : 
        temp = temp >> 1
        m -= 1
    return m
def bitcounter(n) :
    m = getLeftmostBit(n) 
    return _countSetBits(n, m) 
def _countSetBits(n, m) :
    if (n == 0) : 
        return 0
    m = getNextLeftmostBit(n, m)
    if (n == (1 << (m + 1)) - 1) : 
        return ((m + 1) * (1 << m))
    n = n - (1 << m)
    return (n + 1) + bitcounter(n) + m * (1 << (m - 1)) 

def log_two(n): 
    return(math.log(n) / math.log(2))

#-----------------------------------------------------------------------#
        
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()

Submission status: Wrong Answer

Solution code:


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

a.sort(reverse=True)
ans = 0

if a[n - 1] == 1:
    print("1")
else:
    for i in range(n - 1):
        if a[i] != a[i + 1]:
            for j in range(n):
                if a[i] % a[n - j - 1] == 0 and i != n - j - 1:
                    break
                if j == n - 1:
                    ans += 1
    if a.count(a[n - 1]) < 2:
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
p = list(map(int,input().split()))
p.sort(reverse=True)
count=0
if np.unique(p).size >1:
    count +=1
for i in range(len(p)):
    for j in reversed(range(i+1,len(p))):
        if p[i]< p[j]*2 and not p[i]==p[j]:
            count +=1
            break
        if p[i]%p[j] ==0:
            break
        if j == i+1:
            count +=1
if count >=1:
    print(count)
else:
    print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
if len(set(a)) != n:
  print(0)
else:
  
  a.sort()
  e = []
  while len(a):
    b = a.pop(0)
    for i in a:
      if i % b == 0:
        a.pop()
    e.append(b)
  print(len(e))

Submission status: Wrong Answer

Solution code:
import sys


N=int(input())
#print(N)
A=input().split()
A_int = [int(s) for s in A]
print(A_int)
Odd=[]
Even=[]
for factor in A_int:
  if factor%2==0:
    Even.append(factor)
  else:
    Odd.append(factor)
#print(Odd)
#print(Even)

#ここから本題
#print(A_int[2])
outcount=0
evencount=0
oddcount=0
for fact in A_int:
  evencount=0
  oddcount=0
  
  if fact%2==0:
    for even in Even:
      if fact%even==0:
        evencount+=1
      if evencount==2:
        outcount+=1
        break
  else:
    for odd in Odd:
      if fact%odd==0:
        oddcount+=1
      if oddcount==2:
        outcount+=1
        break
    
      
print(N-outcount)

Submission status: Wrong Answer

Solution code:
N = int(input())
nums = list(map(int, input().split()))
count = [0]*N
nums.sort()
for i in range(N):
  fNum = nums[i]
  for j in range(0,N):
    if (nums[j] > fNum):
      break
    if (count[i] == 1):
      continue
    else:
      sNum = nums[j]
      if (fNum%sNum == 0):
      	count[i] += 1
answer = 0
print(count)
for i in count:
  if (i == 0):
    answer += 1
print(answer)

Submission status: Wrong Answer

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

A.sort()
A_set = set(A)
count = 0
last_num = 0
flag = True
now_num = 0
half_num = 0
min_num = A[0]
count_flag = False

if A.count(1) == 1:
    print(1)
    exit()
for i in range(N):
    count_flag = True
    now_num = A[i]
    half_num = A[i]/min_num
    if now_num == last_num:
        if flag:
            count -= 1
            flag = False
    else:
        for j in range(0, i):
            if A[j] > half_num:
                break
            if now_num % A[j] == 0:
                count_flag = False
                break
        if count_flag:
            if not flag:
                flag = True
            count += 1
        last_num = A[i]
print(count)

Submission status: Wrong Answer

Solution code:
import sys 
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def main():
    n = I()
    a = LI()
    ava = [1]*n
    for i in range(n):
        for j in range(i+1,n):
            if i==j:    continue
            if not ava[i] and not ava[j]:
                break
            if ava[i]:
                if not a[i]%a[j]:
                    ava[i] = 0
            if ava[j]:
                if not a[j]%a[i]:
                    ava[j] = 0
    print(ava.count(1))
    return

if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

A.sort()
max_num = max(A)
sub_count = [x for x in set(A) if A.count(x) > 1]

i = 0
count = 0
while True:
    if len(A) == 0 or A[0] == max:
        break
    count += 1
    look = A[0]
    del A[0]
    del_num = []
    for j in range(len(A)):
        if A[j] % look == 0:
            del_num.append(j)
    del_num = sorted(del_num, reverse=True)
    for j in del_num:
        del A[j]

print(count - len(sub_count))

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
A.sort()
results = []

while(A):
  a = A.pop(0)
  print(a)
  if a in A:
    A = [i for i in A if i!=a]
  else:
    results.append(a)
  A = [i for i in A if i%a!=0]
print(len(results))

Submission status: Wrong Answer

Solution code:
"""
def factorization(l,x):
    arr = []
    temp = x
    for i in range(2, int(-(-x**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([x, 1])

    return arr
"""

def solve():
#    memo = [1]*n
    cnt = 0
    for l in range(N):
        if A[l] < n:
            continue
        for k in range(2,n+1):
            if A[l]%k == 0 and A[l] > k:
                cnt += 1
                break
    print(cnt)

if __name__=="__main__":
    n = int(input())
    a = list(map(int, input().split()))
    A = list(set(a))
#    print(A)
    N = len(A)
#    print(N)

    solve()

Submission status: Wrong Answer

Solution code:
import itertools
import decimal
import math
import collections
import sys
input = sys.stdin.readline

N=int(input())

ListA=list(map(int,input().split()))
ListA.sort()#reverse=True)

ans=N
rootN=int(math.sqrt(N))
for i in range(N):
    if(i < N-1):
        if(ListA[i]==ListA[i+1]):
            ans-=1
            continue

    if(i>=1):
        if(ListA[i]==ListA[i-1]):
            ans-=1
            continue
        
    rootA=math.sqrt(ListA[i])

    for j in range(i):
        if(ListA[i]%ListA[j]==0):
            ans-=1
            break
        if(ListA[j]>rootA):
            break

    
# if(N>=2):
#     if(ListA[2]%ListA[1]==0):
#         ans-=1

print(ans)

Submission status: Wrong Answer

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

sum = 0

if N == 1:
    print(1)

else:
    while True:
        X = A.pop(0) #左端をとる
    
        i = len(A)

        OK = True

        for Y in reversed(A):
            i -= 1

            if Y == X:
                OK = False
                A.pop(i)

            elif Y%X == 0:
                A.pop(i)

        if OK:
            sum += 1

        if len(A) == 0:
            break

    print(sum)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = n
dic = {}
for i in range(n):
    if a[i] not in dic.keys():
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1
flag = True
for i in range(n-1):
    if a[i] != a[i+1]:
        flag = False
        break
if n == 1:
    cnt = 1
elif flag:
    cnt = 0
else:
    l = []
    res = list(dic.keys())
    chk = [0 for i in range(len(res))]
    for i in range(len(res)):
        if dic[res[i]] >= 2:
            cnt -= dic[res[i]]
            chk[i] = 2
    for i in res:
        l.append(make_divisors(i)[1:])
    for i in range(len(res)):
        for j in range(i+1, len(l)):
            if chk[j] == 0:
                for k in range(len(l[j])):
                    if res[i] == l[j][k]:
                        cnt -= dic[res[i]]
                        chk[j] = 1
                        break
print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

def pri_me(x):
    if x == 2:
        return True
    for i in range(2,int(x**0.5)+1):
        if x%i==0:
            return False
    return True

n = int(input())
a=list(map(int,input().split()))
a=sorted(a)
c=Counter(a)
x=set()
for i in range(n):
    x.add(a[i])
ans = 0
for i in range(n):
    if c[a[i]]>1:
        continue
    if pri_me(a[i]):
        ans += 1
        continue
    l=make_divisors(a[i])
    x.remove(a[i])
    f=1
    for r in l:
        if r in x:
            f=0
            break
    if f:
        ans += 1
    x.add(a[i])
print(ans)

Submission status: Wrong Answer

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

sum =0
for i,n in enumerate(a):
    flag = True
    for j in a[i+1:]:
        if(n%j==0):
            flag=False
            break
    if(i==len(a)-1):
        if(a[i-1]==n):
            flag=False
    if(flag):
        sum+=1
print(sum)

Submission status: Wrong Answer

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

a.sort(reverse=True)

ans = 0
for index, i in enumerate(a):
    if index+1 != len(a):
        for j in a[index+1:]:
            if i % j == 0:
                break
            elif j == a[-1]:
                ans += 1
    else:
        if i % a[index-1] != 0:
            ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
An = list(map(int, input().split()))
ok = [False] * N
ng = set()
a_An = np.array(An)
for i, a in enumerate(An):
    temp = a_An / a
    temp[i] = 0.1
    check = (temp % 1 == 0)
    ok = ok | check
    print(ok)
    # check = np.delete(check, np.where(check == i))
    # check = check[check != i]
    # if len(check) > 0:
    #     ng = ng | set(check)
ok = list(ok)
print(ok.count(0))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
def map_all(es):
    return all([e == es[0] for e in es[1:]]) if es else False
if map_all(A):
    print(0)
else:
    B = list(set(A))
    l = len(B)
    ct = 1
    for i in range(1,l):
        for j in range(i):
            if B[i]%B[j] == 0:
                break
            elif j == i-1:
                ct = ct +1
    print(ct)

Submission status: Wrong Answer

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

box={}
import math
ans=0
for i in range(n):
    check=True
    for k in box:
        if A[i]%k==0:
            check=False
            break
    if i!=n-1:
        if A[i]==A[i+1]:
            check=False
    else:
        if A[i]==A[i-1]:
            check=False
    if check:
        box[A[i]]=1
        ans+=1

print(ans)

Submission status: Wrong Answer

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

k = 0
b = 0
for l in range(n):
    if a[l] == 1:
        b = b + 1
        
if b == 0:
    for i in range(n):
        for j in range(n):
            if a[i] != 1:
                if i != j:            
                    if a[i] % a[j] == 0:
                        a[i] = 1
                        break
                if j == n-1:
                    k = k + 1          
    print(k)
elif b == 1:
    print('1')
else:
    print('0')

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
cnt=0
v=[]
for i in range(n):
#  if not v:
#    cnt+=1
#    v.append(a[i])
  tmp=True  
  for j in range(len(v)):
    if i==j:
      continue
    
    if a[i]%v[j]==0:
      tmp=False
#      print(tmp,a[i],a[j])
  if tmp:
    cnt+=1
    v.append(a[i])
      
#print(v)
print(len(v))

Submission status: Wrong Answer

Solution code:
import numpy as np
n = int(input())
A = np.array(list(map(int,input().split())))
samples= []

for idx, num in enumerate(A):
  B = num % A
  same = np.count_nonzero(A == num)
  if same == n:
    break
  elif np.count_nonzero(B!=0) == n-same:
    samples.append(num)
    
ans = len(set(samples))    
print(ans)

Submission status: Wrong Answer

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

a = list(set(a))
n = len(a)
cnt = 0
jdg = 1

if len(a) == 1:
    print(cnt)

else:
    for i in range(n):
        for j in range(n):
            if i == j:
                continue
            elif a[i] % a[j] == 0:
                jdg = 0
                break
        if jdg == 1:
            cnt += 1
        jdg = 1
    print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
from collections import defaultdict

input()
A = np.fromstring(input(), int, sep=' ')

counter = defaultdict(int)
for x in A:
    counter[x] += 1

# A = np.array(list(set(A)))
A.sort()

count = 0
f = np.ones_like(A, dtype=bool)
for i, x in enumerate(A):
    if not f[i]:
        continue

    # print(i, x, count, f)
    if counter[x] == 1:
        count += 1

    if x <= 10**3+1:
        f[i+1:] &= (A[i+1:] % x != 0)

print(count)

Submission status: Wrong Answer

Solution code:
n = int(input())
nums = [int(e) for e in input().split()]
import numpy as np
nums.sort()
npnums = np.array(nums)

cnt = 0 #個数のカウント


for i,v in enumerate(nums):
    if np.count_nonzero(v % npnums[:i+1] == 0) > 1:
        cnt +=1
    else:
        continue
print(n-cnt)

Submission status: Wrong Answer

Solution code:
import collections

n = int(input())
d = list(map(int, input().strip().split()))

# 重複しているやつは初めから消しておく
counts = collections.Counter(d)
dic = {a: c == 1 for a, c in counts.items()}

keys = sorted(dic.keys())
last = keys[-1]

for k in keys:
    if dic[k]:
        n = 2
        while k * n <= last:
            if k * n in dic:
                dic[k * n] = False
            n += 1

count = len([True for v in dic.values() if v])
print(count)

Submission status: Wrong Answer

Solution code:
from collections import Counter
a =  int(input())
A = list(map(int, input().split()))
# d_num = a

# A_set = list(set(A))
# if len(A_set) == 1:
#     print(0)
# else:
#     A_count = Counter(A)
#     for i in range(len(A_set)):
#         for j in range(len(A_set)):
#             if(A_set[i]%A_set[j] == 0):
#                 A_set[i] = A_set[j]
#                 if(j != i):
#                     d_num -= A_count[A_set[i]]
#                 break
#     print(d_num)
A.sort()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort()
i = 1
for e in a:
  j = i
  while j<len(a):
    if a[j]%e!=0:
      j += 1
      continue
    else:
      a.remove(a[j])
  i += 1
if len(a)==1 and a[0]!=1:
  print(0)
else:
  print(len(a))

Submission status: Wrong Answer

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

if(len(set(a))==1 and len(a)>1):
    print(0)
    exit()

    
a.sort()
#print(a)

def prime_numbers(m):
    # 素数を保持するset
    primes = set()

    # 2以上m以下の素数を数え上げる
    n = a[0]
    for n in a:
        # 自身より小さい全ての素数で割り切れなければ、素数とみなせる
        if all(n % i != 0 for i in primes):
            primes.add(n)
        n += 1

    return primes


prime=prime_numbers(a[n-1])

print(len(prime))

Submission status: Wrong Answer

Solution code:

from collections import Counter

def divisor(n):
    tank = []
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            tank.append(i)
            if i!=n//i:
                tank.append(n//i)
    tank.sort()
    return tank

n = int(input())
A = list(map(int,input().split()))
A = sorted(A)
c = Counter(A)
lst = []
for k,v in c.items():
    if v==1:
        lst.append(k)

if len(lst)==0:
    print(0)
    
else:
    cnt = 0
    prime = set()
    
    div = []
    for x in lst:
        div.append(set(divisor(x)))
    
    for x,d in zip(lst, div):
        if len(prime & d)==0:
            cnt += 1
            prime = prime.union(set([x]))
    print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
ansList = [1]*n
C = Counter(a)

if C[a[0]] == n:
    print(0)
    sys.exit()

for i in range(n):
    if ansList[i] == 1:
        for j in range(i+1,n):
            if a[i]%a[j] == 0:
                ansList[i] = 0
            if a[j]%a[i] == 0:
                ansList[j] = 0

c = Counter(ansList)
print(c[1])

Submission status: Wrong Answer

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

mul=1
ans=[0]*len(As)
for i in range(len(As)-1):
    if As[i+1]==As[i]:
        ans[i+1]+=1
        ans[i]+=1
    for j in range(len(As)-1,i,-1):
        print(i,j)
        if As[j]%As[i]==0:
            ans[j]+=1
        if As[i]*mul>As[j]:
            break
    mul*=As[i]
print(ans.count(0))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n = int(input())
As  = list(map(int, input().split()))
if n == 1:
    print(0)
    exit()

Ss = sorted(As)
primes = set()
cnt = 0
d = defaultdict(int)
As = [False] * (10**6+10)
for s in Ss:
    d[s] += 1
    # if d[s] == 2:
    #     As[s] = True
# print(Ss)
for s in set(Ss):
    if As[s]:continue
    else:
        if d[s] == 1:
            cnt += 1
        ind = 1
        while s * ind <= 10**6:
            As[s*ind] = True
            ind += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
# スペース区切りの整数の入力
N = int(input())
A = np.array(list(map(int, input().split())))

Ainv = 1/A 

count = 0
while len(A) > 0:
    a = A[0]
    ai = Ainv[0]
    A = A[1:]
    Ainv = Ainv[1:]
    
    # a で割り切れない部分
    f1 = A % a > 0
    # a を割り切れない部分
    f2 = (Ainv * a)%1 > 0 
        
    # 0がなければCountする
    if np.sum(f2 == 0) == 0:
        count += 1

    # AとAinvの不要な箇所を削除
    A = A[f1]
    Ainv = Ainv[f1]

print(count)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(x) for x in input().split()]
from collections import defaultdict
d = defaultdict(int)
ans = 0
for i in range(N):
    if d[a[i]] == 0:
        d[a[i]] = 1
    else:
        d[a[i]] = -1
for i in range(1,1001):
    if d[i] == 1:
        ans += 1
        for j in range(2,1+10**6//i):
            d[j*i] = 0
for i in range(1001,1000000):
    if d[i] == 1:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n = int(input())
a = list(map(int,input().split()))
b = set()
if len(set(a)) != n:
    print(0)
    exit()
a.sort()
cnt = 0

for i in a:
    flg = True
    l = set(make_divisors(i))
    if len(l & b) == 0:
        cnt += 1
    b.add(i)
print(cnt)

Submission status: Wrong Answer

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

ans = 0
for i in range(n):
    if i == 0 and n > 1:
        if A[i] % A[i+1] != 0:
            ans += 1
    for j in range(i):
        if A[i] % A[j] == 0:
            break
        if j == i - 1:
            if j + 2 < n:
                if A[i] % A[j+2] != 0:
                    ans += 1
            else:
                ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = sorted([int(x) for x in input().split()], reverse=True)
ans = 0
if N != 1 and A[-1] == A[-2]: 
    ans -= 1
while len(A):
    a = A.pop()
    ans += 1
    A = list(filter(lambda x: x%a != 0, A))
print(ans)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
L = [int(s) for s in input().rstrip().split(' ')]
#重複消す
D = collections.Counter(L)
L_0 = []
S = list(set(L))
for x in S:
    if D[x] == 1:
        L_0.append(x)
if L_0 == []:
    print(0)
else:
    L_0.sort()
    ans = 0
    while len(L_0) > 0:
        if 2*L_0[0] > L_0[-1]:
            ans += len(L_0)
            L_0 = []
        else:
            for y in reversed(L_0[1:]):
                if y % L_0[0] == 0:
                    L_0.remove(y)
            L_0.remove(L_0[0])
            ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
mod0 = [1] * N
for i in range(N):
    if mod0[i] == 0:
        continue
    for j in range(1,N - i):
        if mod0[i+j] == 0:
            continue
        if A[i + j] % A[i] == 0:
            mod0[i + j] = 0
cnt = 0
for i in set(A):
    if A.count(i) > 1:
        cnt += 1
print(sum(mod0) - cnt)

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = sorted(A, reverse=True)
count = 0
for i in range(N):
    flag = True
    for j in range(N):
        if j > i:
            if B[i] % B[j] == 0:
                flag = False
                break
    if (i != N-1) and flag:
        count += 1
    if (i == N-1) and (B[N-1] < B[N-2]) and flag:
      	count += 1
print(count)

Submission status: Wrong Answer

Solution code:
import copy
from collections import Counter

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

candidate = set(seq)
counter = Counter(seq)

for k, v in counter.items():
    if v > 1:
        candidate.remove(k)
count = 0

for x in sorted(candidate):
    if x not in candidate:
        continue
    l = list(candidate)
    idx = l.index(x)
    for y in l[idx+1:]:
        if y % x == 0:
            candidate.remove(y)

print(len(candidate))

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A.sort()
ans = 0
if len(set(A))==1:
    print(0)
else:
    while len(A)>0:
        p = A[0]
        A = [j for j in A if j % p !=0]
        ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n

for i in range(n):
    if done[i]==1:
        break
    for j in range(i+1,n):
        if done[j] != 1:
            if li[j]==li[i]:
                done[i]=1
                done[j]=1
                dp[i]=0
                dp[j]=0
            elif li[j]%li[i]==0:
                done[j]=1
                dp[j]=0
 
print(sum(dp))

Submission status: Wrong Answer

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

iter = 0

for i in a:
  lst = [i%j for j in a]
  if lst.count(0) == 1:
    iter = iter + 1
print(iter)

Submission status: Wrong Answer

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

if n == 1:
    print(1)
    exit()

b = [True]*n
fix = [False]*n
for i in range(n):
    if not b[i] or fix[i]:
        continue
    if i < n-1 and a[i] == a[i+1]:
        b[i] = False
        fix[i] = True
    for j in range(i+1, n):
        if fix[j]:
            continue
        if a[i] < a[j] < a[i]*2:
            fix[j] = True
            continue
        if a[j] % a[i] == 0:
            fix[j] = True
            b[j] = False

print(sum(b))

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from itertools import *
import copy

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

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

N = I()
A = LI()
ans = 0

for i, kazu in enumerate(A):
    div = make_divisors(kazu)
    d = deque(div)
    d.pop()
    div = list(d)
    temp = copy.deepcopy(A)
    print(temp,div)
    
    l1_l2_and = set(temp) & set(div)
    
    if len(l1_l2_and) == 0:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import collections

def II(): return int(input())
def MI(): return map(int,input().split())
def LI(): return list(map(int,input().split()))
def TI(): return tuple(map(int,input().split()))
def RN(N): return [input().strip() for i in range(N)]


def main():
    
    N = II()
    A = LI()
    As = sorted(A, reverse=True)
    ans = N
    c = collections.Counter(As)
    if len(set(A)) == 1:
        print(0)
    elif c[1] != 0:
        if c[1] == 1:
            print(1)
        else:
            print(0)
    else:
        for i in range(N-1):
            k = N-1
            if c[As[i]] >= 2:
                ans -= 1
                if i == N-2:
                    ans -= 1
            else:
                for j in range(N):
                    if k == i:
                        break
                    if As[i] % As[k] == 0:
                        ans -= 1
                        break

                    k -= 1

        print(ans)


if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
from collections import Counter
def divisor(n):
    fac = []
    for i in range(1,int(n**0.5)+1):
        if n%i == 0: 
            fac.append(i)
            if i*i != n: fac.append(n//i)
    return sorted(fac)
n = int(input())
a = [int(i) for i in input().split()]
c = Counter(a)
na = []
for k,v in c.items():
    if v == 1: na.append(k)
na.sort()
s = set()
ans = 0
for i in range(len(na)):
    for f in divisor(na[i]):
        if f in s: break
    else:
        ans += 1
    s.add(na[i])
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
ans = n
for i in range(n-1):
    if i>0:
        if a[i-1] == a[i] and (a[i] != a[i+1] or i==n-2):
            ans-=1
    for j in range(n-1,i,-1):
        if a[i]%a[j]==0:
            ans-=1
            break
print(ans)

Submission status: Wrong Answer

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

def main():
    ans = 0
    if N == 1:
        print(0)
        return
    else:
        if A[0] != A[1]:
            ans += 1
    for i in range(1, N):
        flag = True
        for j in range(i):
            if A[i]%A[j] == 0:
                flag = False
                break
        if flag:
            ans += 1
    print(ans)
main()