結果

問題 No.1250 汝は倍数なりや?
ユーザー direwolf7direwolf7
提出日時 2020-10-09 23:04:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,582 bytes
コンパイル時間 903 ms
コンパイル使用メモリ 82,064 KB
実行使用メモリ 237,696 KB
最終ジャッジ日時 2024-07-20 13:54:05
合計ジャッジ時間 26,576 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 433 ms
188,672 KB
testcase_01 AC 435 ms
188,800 KB
testcase_02 AC 444 ms
188,800 KB
testcase_03 AC 440 ms
188,672 KB
testcase_04 AC 440 ms
188,672 KB
testcase_05 AC 435 ms
188,800 KB
testcase_06 AC 438 ms
188,800 KB
testcase_07 AC 435 ms
188,800 KB
testcase_08 AC 429 ms
188,416 KB
testcase_09 AC 428 ms
188,672 KB
testcase_10 AC 428 ms
188,800 KB
testcase_11 WA -
testcase_12 AC 415 ms
188,544 KB
testcase_13 AC 429 ms
188,928 KB
testcase_14 AC 437 ms
188,672 KB
testcase_15 WA -
testcase_16 AC 418 ms
188,416 KB
testcase_17 AC 438 ms
188,544 KB
testcase_18 AC 437 ms
188,672 KB
testcase_19 AC 426 ms
188,416 KB
testcase_20 AC 427 ms
189,016 KB
testcase_21 WA -
testcase_22 AC 430 ms
188,544 KB
testcase_23 AC 435 ms
189,312 KB
testcase_24 AC 436 ms
190,848 KB
testcase_25 AC 448 ms
189,952 KB
testcase_26 AC 442 ms
189,312 KB
testcase_27 AC 448 ms
191,360 KB
testcase_28 WA -
testcase_29 AC 437 ms
188,928 KB
testcase_30 AC 432 ms
190,080 KB
testcase_31 AC 443 ms
188,728 KB
testcase_32 AC 450 ms
190,208 KB
testcase_33 AC 535 ms
237,696 KB
testcase_34 AC 492 ms
218,368 KB
testcase_35 AC 518 ms
230,272 KB
testcase_36 AC 521 ms
233,600 KB
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 496 ms
218,112 KB
testcase_40 AC 491 ms
218,240 KB
testcase_41 WA -
testcase_42 WA -
testcase_43 AC 525 ms
233,320 KB
testcase_44 AC 482 ms
212,736 KB
testcase_45 AC 527 ms
233,532 KB
testcase_46 WA -
testcase_47 AC 492 ms
220,516 KB
testcase_48 AC 453 ms
188,544 KB
testcase_49 AC 455 ms
188,288 KB
testcase_50 AC 454 ms
188,800 KB
testcase_51 AC 446 ms
188,416 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import os, sys
from io import IOBase, BytesIO
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
 
# Cout implemented in Python
import sys
class ostream:
    def __lshift__(self,a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

def get_input(a=str):
    return a(input())

def get_int_input():
    return get_input(int)

def get_input_arr(a):
    return list(map(a, input().split()))

def get_int_input_arr():
    return get_input_arr(int)


def sieve(n):
    primes = [-1] * (n)
    primes[0] = -1
    primes[1] = -1
    
    i = 2
    sqrt_n = int(n ** 0.5 + 1)
    prime_nums = []
    while i <= sqrt_n:
        if primes[i] == -1:
            primes[i] = 1
            prime_nums.append(i)
            for j in range(i * i, n, i):
                primes[j] = 2
        i += 1
    for i in range(sqrt_n, n):
        if primes[i] == -1:
            primes[i] = 1
            prime_nums.append(i)
    return prime_nums

def get_prime_fac(primes, num):
    freq = {}
    for prime in primes:
        if prime <= num and num > 1:
            r = 0
            while num % prime == 0 and num > 1:
                r += 1
                num = num // prime
            if r > 0:
                freq[prime] = r
        else:
            break
    return freq

from collections import defaultdict

def solve():
    prime_nums = sieve(10 ** 7)

    n, h = get_int_input_arr()

    arr = get_int_input_arr()

    h_freq = get_prime_fac(prime_nums, h)

    for i in range(len(arr)):
        for p_h in h_freq:
            while h_freq[p_h] > 0 and arr[i] > 1 and arr[i] % p_h == 0:
                arr[i] = arr[i] // p_h
                h_freq[p_h] -= 1
    
    res = True
    for i in h_freq:
        if h_freq[i] > 0:
            res = False
            break
    if res:
        cout<<"YES"<<endl
    else:
        cout<<"NO"<<endl






def main():
    solve()


if __name__ == "__main__":
    main()
0