結果
問題 |
No.1006 Share an Integer
|
ユーザー |
|
提出日時 | 2020-03-06 23:15:07 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,110 bytes |
コンパイル時間 | 223 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 59,364 KB |
最終ジャッジ日時 | 2024-10-14 09:43:51 |
合計ジャッジ時間 | 4,265 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | AC * 1 WA * 7 TLE * 1 -- * 10 |
ソースコード
def prime(n,p): iteral = 0 while n%p == 0: n //= p iteral += 1 return iteral from collections import deque def makeprime(N): if N == 2: ans = set([2]) return ans else: ans = deque([2*i+1 for i in range(1,N//2+1) if 2*i+1 <= N]+[2]) while ans[0] != max(ans): v = ans.popleft() tmp = set([v*i for i in range(1,len(ans)//v+1) if i*v <= len(ans)]) ans = deque(set(ans)-tmp) return ans def main(): X = int(input()) lis = makeprime(X//2+1) ans = [] val = 2**60 for i in range(1,X//2+1): s1 = 1 s2 = 1 for v in lis: if v <= i: s1 *= (prime(i,v)+1) if v <= X-i: s2 *= (prime(X-i,v)+1) tmp = abs(s1-s2) if tmp < val: val = tmp ans = [] ans.append((i,X-i)) elif tmp == val: ans.append((i,X-i)) while ans: x = ans.pop(0) print(x[0],x[1]) if __name__ == '__main__': main()