結果

問題 No.1006 Share an Integer
ユーザー hedwig100hedwig100
提出日時 2020-04-06 21:59:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 736 ms / 2,000 ms
コード長 1,612 bytes
コンパイル時間 291 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 113,780 KB
最終ジャッジ日時 2024-07-07 02:42:11
合計ジャッジ時間 10,637 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 197 ms
99,328 KB
testcase_01 AC 196 ms
99,840 KB
testcase_02 AC 196 ms
100,992 KB
testcase_03 AC 194 ms
99,328 KB
testcase_04 AC 196 ms
101,888 KB
testcase_05 AC 202 ms
102,656 KB
testcase_06 AC 205 ms
103,552 KB
testcase_07 AC 200 ms
102,784 KB
testcase_08 AC 195 ms
102,784 KB
testcase_09 AC 199 ms
102,912 KB
testcase_10 AC 197 ms
103,040 KB
testcase_11 AC 495 ms
106,744 KB
testcase_12 AC 714 ms
112,676 KB
testcase_13 AC 736 ms
113,648 KB
testcase_14 AC 736 ms
113,688 KB
testcase_15 AC 668 ms
113,512 KB
testcase_16 AC 416 ms
107,504 KB
testcase_17 AC 494 ms
109,260 KB
testcase_18 AC 670 ms
111,072 KB
testcase_19 AC 657 ms
110,924 KB
testcase_20 AC 679 ms
111,424 KB
testcase_21 AC 729 ms
113,780 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def sieve_advance(n):  #n未満の整数iについてi以下でiを割り切る最小の素数を求める。
    minfactor = [-1] * n
    minfactor[0],minfactor[1] = 0,1
    isprime = [True] * n
    isprime[0],isprime[1] = False,False

    for i in range(2,n):
        if isprime[i]:
            minfactor[i] = i
            for j in range(i**2,n,i):
                isprime[j] = False
                if minfactor[j] == -1:
                    minfactor[j] = i
    
    return minfactor

def prime_factor(n,minfactor): #nをminfactorを利用して素因数分解する
    cnt = 1
    while n != 1:
        prime = minfactor[n]
        exp = 0
        while minfactor[n] == prime:
            exp += 1
            n //= prime
        cnt *= (exp + 1)

    return cnt

def main():
    x = int(input())
    minfactor = sieve_advance(2000000)
    dif = INF
    dic = {}
    for i in range(1,x//2 + 1):
        d1 = prime_factor(i,minfactor)
        d2 = prime_factor(x - i,minfactor)
        tmp = abs(2 * i - x - d1 + d2)
        if dif >= tmp:
            dif = tmp
            if tmp in dic:
                dic[tmp].append((i, x - i))
                if x != 2 * i:
                    dic[tmp].append((x - i,i))
            else:
                dic[tmp] = [(i,x - i)]
                if x != 2 * i:
                    dic[tmp].append((x - i,i))
    
    ans = dic[dif]
    ans.sort(key = lambda x:x[0])
    for i in range(len(ans)):
        print(*ans[i])

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