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 sys
input = sys.stdin.readline
import math
from collections import defaultdict

n = map(int, input())
a = list(map(int, input().split()))
N = 1000005
b = [0] * N

d = defaultdict(int)
for x in a:
    d[x] += 1

for x in d:
    for j in list(range(2, N)):
        if x * j >= N or b[x * j] == 1: #debuged
            break
        else:
            b[x * j] = 1

ans = 0
for x in a:
    if b[x] == 1:
        continue
    else:
        if d[x] >= 2:
            continue
        else:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import math
from collections import defaultdict

n = map(int, input())
a = list(map(int, input().split()))
a2 = list(set(a))
b = [0] * 1000005
for x in a2:
    for j in list(range(2, 1000005)):
        if x * j > 100005:
            break
        else:
            b[x * j] = 1
ans = 0
for x in a:
    if b[x] != 1:
        ans += 1
d = defaultdict(int)
for x in a:
    d[x] += 1
for x in d:
    if d[x] != 1:
        ans -= d[x]
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from collections import Counter
n=int(input())
b=sorted(list(map(int,input().split())))
a=Counter(b)
mA=b[-1]
acc=0
dp=[True]*(mA+1)
for i,v in a.items():
  if dp[i]==True and v==1:
    acc+=1
  else:dp[i]=False
  if i!=1:
    for k in range(mA//i+1):
      dp[k*i]=False
print(acc)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from collections import Counter
n=int(input())
b=sorted(list(map(int,input().split())))
a=Counter(b)
mA=max(b)
acc=0
dp=[True]*(mA+1)
for i,v in a.items():
  if dp[i]==True and v==1:
    acc+=1
  else:dp[i]=False
  if i!=1:
    for k in range(2,mA//i+1):
      dp[k*i]=False
print(acc)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from collections import Counter
n=int(input())
b=sorted(list(map(int,input().split())))
a=Counter(b)
mA=max(b)
acc=0
dp=[True]*(mA+1)
for i,v in a.items():
  if dp[i]==True and v==1:
    print(i)
    acc+=1
  else:dp[i]=False
  if i!=1:
    for k in range(2,mA//i+1):
      dp[k*i]=False
print(acc)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from collections import Counter
n=int(input())
b=list(map(int,input().split()))
a=Counter(b)
mA=max(b)
acc=0
dp=[True]*(mA+1)
for i,v in a.items():
  if dp[i]==True and v==1:
    acc+=1
  else:dp[i]=False
  if i!=1:
    for k in range(2,mA//i+1):
      dp[k*i]=False
print(acc)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
y=set(a)
acc=0
if a[0]==1:acc+=1
dp=[True]*(a[-1]+1)
for i in range(2,a[-1]+1):
  if i in y:
    if dp[i]==True:
      idx=bisect(a,i)
      if a[idx-1]==a[idx-2]:
        dp[i]=False
      else:acc+=1
    dp[2*i::i]=[False]*len(dp[2*i::i])
print(acc)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
y=set(a)
acc=0
dp=[True]*(a[-1]+1)
for i in range(2,a[-1]+1):
  if i in y:
    if dp[i]==True:
      idx=bisect(a,i)
      if a[idx-1]==a[idx-2]:
        dp[i]=False
      else:acc+=1
    dp[2*i::i]=[False]*len(dp[2*i::i])
print(acc)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n=int(input())
a=sorted(list(map(int,input().split())))
y=set(a)
acc=0
dp=[True]*(a[-1]+1)
for i in range(2,a[-1]+1):
  if i in y:
    if dp[i]==True:
      idx=bisect(a,i)
      if a[idx-1]==a[idx-2]:
        dp[i]==False
      else:acc+=1
    dp[2*i::i]=[False]*len(dp[2*i::i])
print(acc)

Submission status: Wrong Answer

Solution code:
n=int(input())
a=sorted(list(map(int,input().split())))
y=set(a)
acc=0
dp=[True]*(a[-1]+1)
for i in range(2,a[-1]+1):
  if i in y:
    if dp[i]==True:acc+=1
    dp[2*i::i]=[False]*len(dp[2*i::i])
print(acc)

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    liste = [int(x) for x in input().split()]
    if sum(liste)//liste[0]==liste[0]:
        return 0
    mm = 0
    compteur =0
    sad = False
    for loop in range(n):
        for i in range(n):
            if liste[loop]%liste[i]==0:
                compteur += 1
                if compteur ==2:
                    sad = True
                    break
        if not sad:
            mm += 1
        sad = False
        compteur = 0
                
    return (mm)
print(main())

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import sqrt


def main():
    N = int(input())
    np_a = np.array([int(x) for x in input().split()])

    # サイズが 1 = 自分以外で割れないので答えは1
    if np_a.size == 1:
        print(1)
        exit()

    uq = np.unique(np_a)
    check_max = sqrt(10**6)

    while uq.size > 0:
        # 最大値の素因数分解の最大まで
        if uq[0] > check_max:
            break
        # 割り切れる数、自分と同じ数以外のものを消していく
        np_a = np.delete(np_a, np.where(
            (np_a % uq[0] == 0) & (np_a != uq[0]))[0])
        uq = np.delete(uq, np.where((uq % uq[0] == 0))[0])

    uq, count = np.unique(np_a, return_counts=True)
    print(len(uq[count == 1]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections
n = int(raw_input())
ais = map(int,raw_input().split())
ais.sort()
cc = collections.Counter(ais)
s = {ai:True for ai in ais}
m = max(ais)
for a in cc:
	c = a if cc[a] > 1 else 2 * a
	while(c <= m):
		if a in s: s[a] = False
		c+= a
count = 0
for ai in s:
	if s[ai]:
		count +=1
print count

Submission status: Wrong Answer

Solution code:
from collections import Counter
N = int(input())
anslist = set([])
A = set(list(map(int, input().split())))
N = len(A)
Amax = max(A)
for i in A:
    j = 2*i
    while j <= Amax:
        anslist.add(j)
        j += i

A = list(A)
anslist = list(anslist)
anslist.extend(A)
anslist = Counter(anslist)
ans = Counter(anslist.values())
if ans[2] == 0:
    print(0)
else:
    print(N-ans[2])

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in A:
    cont = True
    for j in A:
        if i != j and i % j == 0: cont = False; break
    if cont: ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')


n = int(input())
seq = [int(x) for x in input().split()]
ans = 0
if n == 1:
    pass
else:
    # remove duplicates
    d = {}
    for val in seq:
        try:
            d[val] += 1
        except:
            d[val] = 1
    # seq = [key for key in d if d[key] == 1]
    seq = sorted(set(seq))
    try:
        lst = [False for _ in range(seq[-1]+1)]
        for val in seq:
            f = 2
            newval = val*f
            while newval <= seq[-1]:
                lst[newval] = True
                f += 1
                newval = val*f
        for val in seq:
            if not lst[val] and d[val] == 1:
                ans += 1
    except IndexError:
        pass
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')


n = int(input())
seq = (int(x) for x in input().split())
ans = 0
if n == 1:
    pass
else:
    # remove duplicates
    d = {}
    for val in seq:
        try:
            d[val] += 1
        except:
            d[val] = 1
    seq = [key for key in d if d[key] == 1]
    seq = sorted(seq)
    try:
        lst = [False for _ in range(seq[-1]+1)]
        for val in seq:
            f = 2
            newval = val*f
            while newval <= seq[-1]:
                lst[newval] = True
                f += 1
                newval = val*f
        for val in seq:
            if not lst[val]:
                ans += 1
    except IndexError:
        pass
print(ans)

Submission status: Wrong Answer

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

def div(n):
    i = 1
    ans = []
    while i*i <= n:
        if (n%i == 0):
            if (n == i*i):
                ans.append(i)
            else:
                ans.extend([i, n/i])
        i += 1
    return sorted(ans) 

n = int(input())
seq = (int(x) for x in input().split())
ans = set()
if n == 1:
    pass
else:
    # remove duplicates
    d = {}
    for val in seq:
        try:
            d[val] += 1
        except:
            d[val] = 1
    seq = [key for key in d if d[key] == 1]

    seq = sorted(seq)
    maxans = 0
    for i in range(len(seq)):
        ok = True
        for val in div(seq[i]):
            if val > maxans:
                break
            if val in ans:
                ok = False
                break
        # for val in ans:
        #     if val * 2 > seq[i]:
        #         break
        #     if seq[i] % val == 0:
        #         ok = False
        #         break
        if ok:
            ans.add(seq[i])
            maxans = seq[i]
print(len(ans))

Submission status: Wrong Answer

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

def div(n):
    i = 1
    ans = []
    while i*i <= n:
        if (n%i == 0):
            if (n == i*i):
                ans.append(i)
            else:
                ans.extend([i, n/i])
        i += 1
    return ans 

n = int(input())
seq = (int(x) for x in input().split())
ans = set()
if n == 1:
    pass
else:
    # remove duplicates
    d = {}
    for val in seq:
        try:
            d[val] += 1
        except:
            d[val] = 1
    seq = [key for key in d if d[key] == 1]

    seq = sorted(seq)

    for i in range(len(seq)):
        ok = True
        for val in div(seq[i]):
            if val in ans:
                ok = False
                break
        # for val in ans:
        #     if val * 2 > seq[i]:
        #         break
        #     if seq[i] % val == 0:
        #         ok = False
        #         break
        if ok:
            ans.add(seq[i])
print(len(ans))

Submission status: Wrong Answer

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
seq = (int(x) for x in input().split())
# remove duplicates
d = {}
for val in seq:
    try:
        d[val] += 1
    except:
        d[val] = 1
seq = [key for key in d if d[key] == 1]

seq = sorted(seq)
ans = []
for i in range(len(seq)):
    ok = True
    for val in ans:
        if val * 2 > seq[i]:
            break
        if seq[i] % val == 0:
            ok = False
            break
    if ok:
        ans.append(seq[i])
print(len(ans))

Submission status: Wrong Answer

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
seq = (int(x) for x in input().split())
d = {}
for val in seq:
    try:
        d[val] += 1
    except:
        d[val] = 1
seq = [key for key in d if d[key] == 1]
seq = sorted(seq)
ans = []
for i in range(len(seq)):
    ok = True
    for val in ans:
        if seq[i] % val == 0:
            if seq[i] == val:
                cnt -= 1
            ok = False
            break
    if ok:
        ans.append(seq[i])
print(len(ans))

Submission status: Wrong Answer

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

a.sort()

table=[True]*1000001
count=0
if n==1:
  count=1
else:
  for i in range(0,n):
    pp=a[i]
    if table[pp]==True:
      if i==0:
        if pp!=a[i+1]:
          count+=1
          for j in range(pp,1000001,pp):
            table[j]=False
      elif i==n-1:
        if pp!=a[n-2]:
          count+=1
      else:
        if pp!=a[i+1] and pp!=a[i-1]:
          count+=1
          for j in range(pp,1000001,pp):
            table[j]=False
      
print(count)

Submission status: Wrong Answer

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

a.sort()

table=[True]*1000001
count=0
if n==1:
  count=1
else:
  for i in range(0,n):
    pp=a[i]
    if table[pp]==True:
      if i==0:
        if a[i]!=a[i+1]:
          count+=1
          for j in range(pp,1000001,pp):
            table[j]=False
      elif i==n-1:
        if a[i]!=a[i-1]:
          count+=1
          for j in range(pp,1000001,pp):
            table[j]=False
      else:
        if a[i]!=a[i+1] and a[i]!=a[i-1]:
          count+=1
          for j in range(pp,1000001,pp):
            table[j]=False
      
print(count)

Submission status: Wrong Answer

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

a.sort()

table=[]
for i in range(1000001):
  table.append([True,0])
count=0
for i in range(0,n):
  if table[a[i]][0]==True:
    count+=1
  if table[a[i]][1]==0:
    table[a[i]][1]=1
    for j in range(a[i],1000001,a[i]):
      table[j][0]=False
  elif table[a[i]][1]==1:
    count-=1
    table[a[i]][1]=2
      
print(count)

Submission status: Wrong Answer

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
collect = collections.Counter(A)
count = 0

dp = [True] * max(A)

for a in A:
    for i in range(a, max(A)+1, a):
        if i != a:
            dp[i-1] = False
    if dp[a-1] and collect[a] == 1:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])
a = [int(s) for s in data[1].split()]
a = sorted(a)

max = a[-1]
print(max)

l = [0]*(max+1)

for i in a:
    l[i] += 1
    if l[i] == 1:
        for j in range(i*2,max+1,i):
            l[j] = 2
print(l.count(1))

Submission status: Wrong Answer

Solution code:
from sys import exit
n = int(input())
a = sorted(list(map(int, input().split())), reverse = True)

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

ans = (0 if a[-1] == a[-2] else 1)
for i in range(n - 1):
    f = True
    for j in range(i + 1, n):
        if a[i] % a[j] == 0:
            f = False
            break
    if f:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

tfs = [True for _ in As]
for i, current in enumerate(As):
    if len(As)<=i+1:
        break
    for j, A in enumerate(As[i+1:]):
        j = j+i+1
        if not tfs[j]:
            break
        if A != current:
            current_tf = A%current
            current_tf = [current_tf!=0][0]
            tfs[j] = current_tf
        else:
            tfs[i] = False
            tfs[j] = False
print(sum(tfs))

Submission status: Wrong Answer

Solution code:
N = int(input())
lis = [1] * (10**7+1)
for i in range(2,10**7+1):
    for j in range(i,10**7+1,i):
        lis[j] += 1
ans = 0
for i in range(1,N+1):
    ans += lis[i] * i
print(ans)

Submission status: Wrong Answer

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

bool_array = []

# bool配列の作成
for i in range(len(As)):
    tmp = [True if i!=j else False for j in range(len(As))]
    bool_array.append(tmp)

count = 0
for i, A in enumerate(As):
    is_exist = True
    for j, tf in enumerate(bool_array[i]):
        if i!=j and not tf:
            is_exist = False
            break
        elif i!=j:
            current_tf = A%As[j]
            current_tf = [current_tf==0][0]
            if current_tf and A!=As[j]:
                is_exist = False
                bool_array[i][j] = False
                #bool_array[j][i] = False
                break
    if not is_exist:
        count+=1
print(count)