#477249 (Python3) No.1006 Share an Integer

• 問題: No.1006 Share an Integer
• ユーザー: Novi
• 提出日時: 2020-05-07 11:55:03
• 言語: Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
• 結果: AC
• 実行時間: 382 ms / 2,000 ms
• コード長: 657 bytes
• コンパイル時間: 84 ms
• コンパイル使用メモリ: 10,796 KB
• 実行使用メモリ: 8,700 KB
• 最終ジャッジ日時: 2023-09-16 07:51:21
• 合計ジャッジ時間: 4,742 ms
• ジャッジサーバーID （参考情報）: judge11 / judge14

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	16 ms; 8,560 KB
testcase_01	AC	16 ms; 8,604 KB
testcase_02	AC	17 ms; 8,576 KB
testcase_03	AC	17 ms; 8,236 KB
testcase_04	AC	17 ms; 8,528 KB
testcase_05	AC	17 ms; 8,556 KB
testcase_06	AC	17 ms; 8,640 KB
testcase_07	AC	17 ms; 8,512 KB
testcase_08	AC	17 ms; 8,460 KB
testcase_09	AC	17 ms; 8,700 KB
testcase_10	AC	17 ms; 8,480 KB
testcase_11	AC	216 ms; 7,916 KB
testcase_12	AC	357 ms; 7,916 KB
testcase_13	AC	379 ms; 7,956 KB
testcase_14	AC	380 ms; 8,132 KB
testcase_15	AC	325 ms; 8,144 KB
testcase_16	AC	162 ms; 8,608 KB
testcase_17	AC	221 ms; 7,964 KB
testcase_18	AC	327 ms; 8,052 KB
testcase_19	AC	314 ms; 7,984 KB
testcase_20	AC	340 ms; 8,024 KB
testcase_21	AC	382 ms; 8,052 KB

ソースコード

import math
x=int(input())

#約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def f(a):
    return a-len(make_divisors(a))
ans=float("inf")
cnt=[]
check=ans
if x==2:
    print(1, 1)
    exit()
for i in range((x//2)-int(math.sqrt(x))-1,(x//2)+int(math.sqrt(x))+1):
    tmp=abs(f(i)-f(x-i))
    if ans>=tmp:
        cnt.append(i)
        ans=tmp
    check=min(check,tmp)

for i in cnt:
    if abs(f(i)-f(x-i))==check and i>0 and x-i>0:
        print(i,x-i)