結果

問題 No.1611 Minimum Multiple with Double Divisors
ユーザー FromBooskaFromBooska
提出日時 2023-08-13 18:49:06
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,192 bytes
コンパイル時間 195 ms
コンパイル使用メモリ 82,188 KB
実行使用メモリ 77,820 KB
最終ジャッジ日時 2024-05-01 11:24:27
合計ジャッジ時間 17,384 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 AC 667 ms
76,476 KB
testcase_02 AC 645 ms
76,440 KB
testcase_03 AC 668 ms
76,644 KB
testcase_04 AC 703 ms
76,456 KB
testcase_05 AC 669 ms
76,776 KB
testcase_06 AC 674 ms
76,772 KB
testcase_07 AC 657 ms
76,252 KB
testcase_08 AC 657 ms
76,396 KB
testcase_09 AC 649 ms
76,244 KB
testcase_10 AC 384 ms
77,188 KB
testcase_11 AC 395 ms
77,604 KB
testcase_12 AC 387 ms
76,844 KB
testcase_13 AC 412 ms
77,272 KB
testcase_14 AC 398 ms
76,660 KB
testcase_15 AC 393 ms
77,820 KB
testcase_16 AC 405 ms
77,652 KB
testcase_17 AC 429 ms
77,168 KB
testcase_18 AC 422 ms
77,172 KB
testcase_19 AC 66 ms
70,236 KB
testcase_20 AC 70 ms
71,784 KB
testcase_21 AC 68 ms
70,928 KB
testcase_22 AC 68 ms
71,140 KB
testcase_23 AC 68 ms
71,236 KB
testcase_24 AC 68 ms
70,856 KB
testcase_25 AC 68 ms
72,364 KB
testcase_26 AC 62 ms
70,364 KB
testcase_27 AC 66 ms
71,432 KB
testcase_28 AC 33 ms
52,884 KB
testcase_29 AC 33 ms
52,952 KB
testcase_30 AC 34 ms
52,680 KB
testcase_31 AC 34 ms
52,240 KB
testcase_32 AC 34 ms
52,952 KB
testcase_33 AC 34 ms
53,288 KB
testcase_34 AC 34 ms
53,180 KB
testcase_35 AC 32 ms
52,388 KB
testcase_36 AC 33 ms
52,480 KB
testcase_37 AC 33 ms
53,016 KB
testcase_38 AC 35 ms
52,880 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Xを素因数分解
# 既存素因数のべき乗を倍にするか、ない素因数を加える
# 10**11ということは37までに存在しない素因数があるはず
# 2*3*5*7*11*13*17*19*23*29*31*37 = 7*10**12
# 必要なのは37までの素因数だけ
# WAだった、2の乗数と3の乗数が両方増えるというパターンがある
# 素因数で考えると、そのコンビネーションもあるから難しい
# 発想の転換、multiplierは37までのどれかの数字にあると考えればいい
# 37超の素因数は無視する

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41]

def low_prime_div_count(num):
    div_count = 1
    for p in primes:
        c = 0
        while num%p == 0:
            num //= p
            c += 1
        div_count *= (c+1)
    return div_count

def main():
    T = int(input())
    for t in range(T):
        X = int(input())
        base = low_prime_div_count(X)
        #print('base', base)
        for n in range(2, 38):
            temp = low_prime_div_count(X*n)
            #print('n', n, 'temp', temp)
            if temp == base*2:
                print(X*n)
                break
                
main()
0