結果
問題 | No.1006 Share an Integer |
ユーザー |
|
提出日時 | 2021-03-06 10:47:03 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,371 bytes |
コンパイル時間 | 224 ms |
コンパイル使用メモリ | 12,544 KB |
実行使用メモリ | 60,416 KB |
最終ジャッジ日時 | 2024-10-08 05:24:02 |
合計ジャッジ時間 | 4,598 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 7 WA * 1 TLE * 1 -- * 10 |
ソースコード
from typing import Listfrom collections import Counterfrom functools import reduceclass SmallestPrimeFactors:def __init__(self, n: int) -> None:self.spf = list(range(n + 1))self.spf[0] = -1self.spf[1] = -1for i in range(2, int(n ** 0.5) + 1):if self.spf[i] == i:for j in range(i * i, n + 1, i):if self.spf[j] == j:self.spf[j] = idef is_prime(self, x: int) -> bool:assert x < len(self.spf)return self.spf[x] == xdef __traverse(self, x: int) -> List[int]:if self.spf[x] == x:return [x]nxt = x // self.spf[x]return self.__traverse(nxt) + [self.spf[x]]def factor(self, x: int) -> List[int]:assert x < len(self.spf)if x < 2:return []return self.__traverse(x)def calc_score(x):cntr = Counter(spf.factor(x))if len(cntr) == 0:return x - 1return x - reduce(lambda x, y: x * y, [v + 1 for v in cntr.values()])x = int(input())spf = SmallestPrimeFactors(x)ans = []cur_min = 1 << 62for i in range(2, x):tmp = abs(calc_score(i) - calc_score(x - i))if tmp < cur_min:ans = [(i, x - i)]cur_min = tmpelif tmp == cur_min:ans.append((i, x - i))for a, b in ans:print(a, b)