結果
問題 | No.2751 429-like Number |
ユーザー |
![]() |
提出日時 | 2024-05-10 21:51:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 565 ms / 4,000 ms |
コード長 | 2,090 bytes |
コンパイル時間 | 278 ms |
コンパイル使用メモリ | 82,436 KB |
実行使用メモリ | 80,820 KB |
最終ジャッジ日時 | 2024-12-20 05:09:02 |
合計ジャッジ時間 | 11,019 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 6 |
other | AC * 22 |
ソースコード
def gcd(a, b):while a:a, b = b%a, areturn bdef is_prime(n):if n == 2:return 1if n == 1 or n%2 == 0:return 0m = n - 1lsb = m & -ms = lsb.bit_length()-1d = m // lsbtest_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]for a in test_numbers:if a == n:continuex = pow(a,d,n)r = 0if x == 1:continuewhile x != m:x = pow(x,2,n)r += 1if x == 1 or r == s:return 0return 1def find_prime_factor(n):if n%2 == 0:return 2m = int(n**0.125)+1for c in range(1,n):f = lambda a: (pow(a,2,n)+c)%ny = 0g = q = r = 1k = 0while g == 1:x = ywhile k < 3*r//4:y = f(y)k += 1while k < r and g == 1:ys = yfor _ in range(min(m, r-k)):y = f(y)q = q*abs(x-y)%ng = gcd(q,n)k += mk = rr *= 2if g == n:g = 1y = yswhile g == 1:y = f(y)g = gcd(abs(x-y),n)if g == n:continueif is_prime(g):return gelif is_prime(n//g):return n//gelse:return find_prime_factor(g)def factorize(n):res = []while not is_prime(n) and n > 1: # nが合成数である間nの素因数の探索を繰り返すp = find_prime_factor(n)s = 0while n%p == 0: # nが素因数pで割れる間割り続け、出力に追加n //= ps += 1res.append(p)if n > 1: # n>1であればnは素数なので出力に追加res.append(n)return resq = int(input())for _ in range(q):n = int(input())res = factorize(n)if len(res) == 3:print("Yes")else:print("No")