結果

問題 No.1006 Share an Integer
ユーザー hedwig100hedwig100
提出日時 2020-04-06 21:59:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 767 ms / 2,000 ms
コード長 1,612 bytes
コンパイル時間 1,105 ms
コンパイル使用メモリ 86,764 KB
実行使用メモリ 114,540 KB
最終ジャッジ日時 2023-09-21 08:19:08
合計ジャッジ時間 11,935 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 225 ms
107,192 KB
testcase_01 AC 231 ms
107,024 KB
testcase_02 AC 235 ms
107,280 KB
testcase_03 AC 229 ms
107,400 KB
testcase_04 AC 233 ms
107,436 KB
testcase_05 AC 229 ms
107,508 KB
testcase_06 AC 225 ms
107,784 KB
testcase_07 AC 229 ms
107,444 KB
testcase_08 AC 233 ms
107,312 KB
testcase_09 AC 237 ms
107,776 KB
testcase_10 AC 229 ms
107,252 KB
testcase_11 AC 528 ms
107,788 KB
testcase_12 AC 744 ms
113,700 KB
testcase_13 AC 767 ms
114,208 KB
testcase_14 AC 759 ms
114,292 KB
testcase_15 AC 686 ms
114,540 KB
testcase_16 AC 448 ms
107,868 KB
testcase_17 AC 529 ms
109,216 KB
testcase_18 AC 690 ms
111,808 KB
testcase_19 AC 682 ms
111,780 KB
testcase_20 AC 696 ms
112,460 KB
testcase_21 AC 749 ms
114,136 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