#798162 (PyPy3) No.2074 Product is Square ?

提出ソース

結果

問題	No.2074 Product is Square ?
ユーザー	kys
提出日時	2022-09-16 22:20:41
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	5,841 bytes
コンパイル時間	156 ms
コンパイル使用メモリ	82,760 KB
実行使用メモリ	161,552 KB
最終ジャッジ日時	2024-12-21 21:35:30
合計ジャッジ時間	94,825 ms
ジャッジサーバーID （参考情報）	judge1 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	46 ms 62,380 KB
testcase_01	TLE	-
testcase_02	TLE	-
testcase_03	TLE	-
testcase_04	TLE	-
testcase_05	TLE	-
testcase_06	TLE	-
testcase_07	TLE	-
testcase_08	TLE	-
testcase_09	TLE	-
testcase_10	TLE	-
testcase_11	TLE	-
testcase_12	TLE	-
testcase_13	TLE	-
testcase_14	TLE	-
testcase_15	TLE	-
testcase_16	TLE	-
testcase_17	TLE	-
testcase_18	TLE	-
testcase_19	TLE	-
testcase_20	TLE	-
testcase_21	TLE	-
testcase_22	TLE	-
testcase_23	TLE	-
testcase_24	TLE	-
testcase_25	TLE	-
testcase_26	TLE	-
testcase_27	TLE	-
testcase_28	TLE	-
testcase_29	TLE	-
testcase_30	TLE	-
testcase_31	TLE	-
testcase_32	AC	91 ms 76,528 KB
testcase_33	AC	120 ms 161,552 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

def main():
    from sys import stdin, setrecursionlimit
    # setrecursionlimit(1000000)
    input = stdin.readline
    def iinput(): return int(input())
    def sinput(): return input().rstrip()
    def i0input(): return int(input()) - 1
    def linput(): return list(input().split())
    def liinput(): return list(map(int, input().split()))
    def miinput(): return map(int, input().split())
    def li0input(): return list(map(lambda x: int(x) - 1, input().split()))
    def mi0input(): return map(lambda x: int(x) - 1, input().split())
    INF = 1000000000000000000
    MOD = 1000000007

    import math
    import random


    class Prime:
        seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

        def is_prime(self, n):
            """
            prime test (hybrid)

            see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

            :param n:
            :return: boolean
            """
            is_prime_common = self.is_prime_common(n)
            if is_prime_common is not None:
                return is_prime_common

            if n < 2000000:
                return self.is_prime_brute_force(n)
            else:
                return self.is_prime_miller_rabin(n)

        def is_prime_common(self, n):
            if n == 1: return False
            if n in Prime.seed_primes: return True
            if any(map(lambda x: n % x == 0, self.seed_primes)): return False

        def is_prime_brute_force(self, n):
            """
            brute force prime test
            use with is_prime_common if you want to skip seed_primes

            :param n:
            :return: boolean
            """
            for k in range(2, int(math.sqrt(n)) + 1):
                if n % k == 0:
                    return False
            return True

        def is_prime_miller_rabin(self, n):
            """
            miller rabin prime test
            use with is_prime_common if you want to skip seed_primes

            see also
                algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
                implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
                improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369

            :param n:
            :return: boolean
            """

            d = n - 1
            while d & 1 == 0:
                d >>= 1

            # use one of these lines / upper is more efficient.
            witnesses = self.get_witnesses(n)
            # witnesses = [random.randint(1, n - 1) for _ in range(100)]

            for w in witnesses:
                y = pow(w, d, n)

                while d != n - 1 and y != 1 and y != n - 1:
                    y = (y * y) % n
                    d <<= 1

                if y != n - 1 and d & 1 == 0:
                    return False

            return True

        def get_witnesses(self, num):
            def _get_range(num):
                if num < 2047:
                    return 1
                if num < 1373653:
                    return 2
                if num < 25326001:
                    return 3
                if num < 3215031751:
                    return 4
                if num < 2152302898747:
                    return 5
                if num < 3474749660383:
                    return 6
                if num < 341550071728321:
                    return 7
                if num < 3825123056546413051:
                    return 9
                return 12

            return self.seed_primes[:_get_range(num)]

        def gcd(self, a, b):
            if a < b:
                return self.gcd(b, a)
            if b == 0:
                return a
            while b:
                a, b = b, a % b
            return a

        @staticmethod
        def f(x, n, seed):
            """
            pseudo prime generator
            :param x:
            :param n:
            :param seed:
            :return: pseudo prime
            """
            p = Prime.seed_primes[seed % len(Prime.seed_primes)]
            return (p * x + seed) % n

        def find_factor(self, n, seed=1):
            """
            find one of factor of n
            this function is based to Pollard's rho algorithm

            see also
                algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
                implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98

            :param n:
            :param seed:
            :return: factor
            """
            if self.is_prime(n):
                return n

            x, y, d = 2, 2, 1
            count = 0
            while d == 1:
                count += 1
                x = self.f(x, n, seed)
                y = self.f(self.f(y, n, seed), n, seed)
                d = self.gcd(abs(x - y), n)

            if d == n:
                return self.find_factor(n, seed+1)
            return self.find_factor(d)

        def find_factors(self, n):
            primes = {}
            if self.is_prime(n):
                primes[n] = 1
                return primes

            while n > 1:
                factor = self.find_factor(n)

                primes.setdefault(factor, 0)
                primes[factor] += 1

                n //= factor

            return primes

    prime = Prime()
    
    for _ in [0] * iinput():
        N = iinput()
        A = liinput()
        tmp = 0
        memo = dict()
        for a in A:
            for k, v in prime.find_factors(a).items():
                if v % 2:
                    if k not in memo:
                        memo[k] = random.randint(1, (1 << 31) - 1)
                    tmp ^= memo[k]
        if tmp:
            print('No')
        else:
            print('Yes')


main()

yukicoder

結果

テストケース

ソースコード