Problem:


問題 4 

　IOI 不動産ではマンションの賃貸を行なっている．
この会社が取り扱うマンションの部屋は 1LDK で，
下図のように面積が 2xy+x+y になっている．
ただし， x, y は正整数である．

　IOI 不動産のカタログにはマンションの面積が昇順に（狭いものから順番に）書かれているが，この中にいくつか間違い（ありえない面積のもの）が混じっていることがわかった．

　カタログ（入力ファイル）は N+1 行で，最初の行に部屋数が書かれていて，
続く N 行に，１行に１部屋ずつ面積が昇順に書かれている．
ただし，
部屋数は 100,000 以下，
面積は (2の31乗)-1 = 2,147,483,647 以下である．
５つの入力データのうち３つまでは，
部屋数 1000 以下，面積 30000 以下である．

　間違っている行数（ありえない部屋の数）を出力しなさい．

　出力ファイルにおいては，
出力の最後の行にも改行コードを入れること．

入出力例

入力例

10
4
7
9
10
12
13
16
17
19
20

出力例

2

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
10
4
7
9
10
12
13
16
17
19
20


Sample output:
2

Submission status: Wrong Answer

Solution code:
'''                                               
  2xy + x + y = z                                 
  (2x + 1) (2y + 1) = 2z + 1                      
  x' * y' = z'                                    
  check z' for prime number.                      
'''                                               
                                                  
prime = dict()                                    
prime_nums = list()                               
                                                  
MAXIMUM = 2**16                                   
def get_prime():                                  
    for i in range(2, MAXIMUM):                   
        if prime.get(i, True):                    
            prime_nums.append(i)                  
            for j in range(i * 2, MAXIMUM, i):    
                prime[j] = False                  
                                                  
                                                  
def check(x):                                     
    x = 2*x + 1                                   
    for prime in prime_nums:                      
        if prime **2 > x:                         
            break                                 
        if x % prime == 0:                        
            return False                          
    print(prime, x)                               
    return True                                   
                                                  
                                                  
get_prime()                                       
n = int(input())                                  
count = 0                                         
for _ in range(n):                                
    if check(int(input())):                       
        count += 1                                
print(count)

Submission status: Wrong Answer

Solution code:
b=[1]*1000000
for i in range(3,1000,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())*2+1]for _ in[0]*int(input())))

Submission status: Wrong Answer

Solution code:
n = int(input())
ng = 0
def prime(a):
    if a == 2: return True
    if a < 2 or a & 1 == 0: return False
    return pow(2, a - 1, a) == 1

for i in range(n):
    a = 2 * int(input()) + 1
    ng += prime(a)
    
print(ng)

Submission status: Accepted

Solution code:
'''                                               
  2xy + x + y = z                                 
  (2x + 1) (2y + 1) = 2z + 1                      
  x' * y' = z'                                    
  check z' for prime number.                      
'''                                               
                                                  
prime = dict()                                    
prime_nums = list()                               
                                                  
MAXIMUM = 2**16                                   
def get_prime():                                  
    for i in range(2, MAXIMUM):                   
        if prime.get(i, True):                    
            prime_nums.append(i)                  
            for j in range(i * 2, MAXIMUM, i):    
                prime[j] = False                  
                                                  
                                                  
def check(x):                                     
    x = 2*x + 1                                   
    for prime in prime_nums:                      
        if prime **2 > x:                         
            break                                 
        if x % prime == 0:                        
            return False                          
    return True                                   
                                                  
                                                  
get_prime()                                       
n = int(input())                                  
count = 0                                         
for _ in range(n):                                
    if check(int(input())):                       
        count += 1                                
print(count)

Submission status: Accepted

Solution code:
a=0
for _ in range(int(input())):
    n=int(input())
    for i in range(1,int(n**0.5)+1):
        if (n-i)%(2*i+1)==0:break
    else:a+=1
print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0590

"""
import sys
from sys import stdin
input = stdin.readline


def main(args):
    # https://www.ioi-jp.org/joi/2005/2006-m2-prob_and_sol/2006-m2-t4-review.html
    invalid_room = 0

    R = int(input())
    for _ in range(R):
        area = int(input())
        valid = False
        x = 1
        while 2 * (x**2 + x) <= area:
            if (area - x) % (2*x + 1) == 0:
                valid = True
                break
            x += 1
        if valid is False:
            invalid_room += 1

    print(invalid_room)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import math

q=[x for x in range(3,2**16) if x%2==1 ]
t=math.sqrt(2**31-1)
p=[2]

while(1):
    pp=q.pop(0)
    if pp>t: break
    p.append(pp)
    q=[x for x in q  if x%pp!=0]
p=p+q

N=int(raw_input())
ans=0
for i in range(N):
    X=int(raw_input())*2+1
    for pp in p:
        if pp>math.sqrt(X):
            ans+=1
            break
        if X%pp==0:
            break
print ans

Submission status: Accepted

Solution code:
a=[int(input())for _ in[0]*int(input())]
m=a[-1]+1
def f(S):
 x=1
 while 2*x*-~x<m:
  if(S-x)%(2*x+1)==0:return 0
  x+=1
 return 1
print(sum(f(S)for S in a))

Submission status: Accepted

Solution code:
a=0
for _ in[0]*int(input()):
 n=int(input())
 for i in range(1,int(n**.5)+1):
  if(n-i)%(2*i+1)==0:break
 else:a+=1
print(a)

Submission status: Accepted

Solution code:
def p(x):
 if x%2==0:return 0
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
print(sum(p(int(input())*2+1)for _ in[0]*int(input())))

Submission status: Accepted

Solution code:
def p(x):
 if x%2==0:return 0
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
def f():print(sum(p(int(input())*2+1)for _ in[0]*int(input())))
if'__main__'==__name__:f()

Submission status: Accepted

Solution code:
def p(x):
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
print(sum(p(int(input())*2+1)for _ in[0]*int(input())))

Submission status: Accepted

Solution code:
b=[1]*500000
for i in range(3,999,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
def p(x):
 if x<5*1e5:return b[x]
 x=2*x+1
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
print(sum(p(int(input()))for _ in[0]*int(input())))

Submission status: Accepted

Solution code:
n = int(input())
ng = 0
def prime(a):
    if a == 1: return 1
    i = 3
    while i <= a / i:
        if a % i == 0:
            return 0
        i += 2
    return 1

for i in range(n):
    a = 2 * int(input()) + 1
    ng += prime(a)
    
print(ng)

Submission status: Accepted

Solution code:
# AOJ 0590: Available Areas
# Python3 2018.6.30 bal4u

def check(s):
	u, v, x = 3, 4, 1
	while v <= s:
		if (s-x)%u == 0: return False
		u += 2
		x += 1
		v += x<<2
	return True

ans = 0
for i in range(int(input())):
	if check(int(input())): ans += 1
print(ans)

Submission status: Accepted

Solution code:

import math
n = input()
ans = 0
for i in range(n):
  s = input()
  for x in range(1, int(math.ceil(math.sqrt(s)))):
    if (s - x) % (2 * x + 1) == 0:
      break
  else:
    ans += 1
print ans

Submission status: Accepted

Solution code:
def isAvailableAreas(area):
	ymax = int(area**0.5)
	for i in range(1, ymax+1):
		if (area-i)%(2*i+1)==0:
			return True
	return False


n = int(input())
A = []
for i in range(n):
	A.append(int(input()))

suma = 0
for i in A:
	if not isAvailableAreas(i):
		suma = suma+1

print(suma)

Submission status: Accepted

Solution code:
def isOddPrime(n):
    for i in range(3,int(n**.5)+1,2):
        if n%i==0:
            return False
    return True
ans=0    
for i in range(int(input())):
    ans+=isOddPrime(2*int(input())+1)
print(ans)

Submission status: Accepted

Solution code:
def check(a):
    for i in range(2,int(a**(1/2))+1):
        if a%i == 0:
            return 1
    return 0
n = int(input())
count = 0
for i in range(n):
    num = int(input())
    if check(2*num+1) == 0:
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
def fact(a): return a and a*fact(a-1) or 1

n,m,r = map(int,input().split())
r-=n*m
if r < 0:
    print(0)
else:
    print(fact(r+n-1)//fact(n-1)//fact(r))

Submission status: Runtime Error

Solution code:
a=[int(input())for _ in[0]*int(input())]
m=a[-1]+1
b=[1]*-~m
x=1
while 2*x*-~x<m:
 y=x
 while 2*x*y+x+y<m:
  b[2*x*y+x+y]=0
  y+=1
 x+=1
print(sum(b[e]for e in a))

Submission status: Runtime Error

Solution code:
b=[1]*2**31
for i in range(3,46341,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))

Submission status: Runtime Error

Solution code:
b=[1]*2**31
for i in range(3,100,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))

Submission status: Runtime Error

Solution code:
b=[1]*(2**31)
for i in range(3,100,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))

Submission status: Runtime Error

Solution code:
b=[1]*10000
for i in range(3,100,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))

Submission status: Runtime Error

Solution code:
b=[1]*1000000
for i in range(3,1000,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))

Submission status: Runtime Error

Solution code:
b=[1]*2**16
for i in range(3,2**8,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))

Submission status: Runtime Error

Solution code:
b=[1]*2**32
for i in range(3,2**16,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
print(sum(b[int(input())]for _ in[0]*int(input())))

Submission status: Runtime Error

Solution code:
b=[1]*500000
for i in range(3,999,2):
 if b[i//2]:b[i*i//2::i]=[0]*len(b[i*i//2::i])
def p(x):
 if x<1e6:return b[x]
 x=2*x+1
 for i in range(3,int(x**.5+1),2):
  if x%i==0:return 0
 return 1
print(sum(p(int(input()))for _ in[0]*int(input())))