結果

問題 No.1006 Share an Integer
コンテスト
ユーザー hedwig100
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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