結果

問題 No.1611 Minimum Multiple with Double Divisors
コンテスト
ユーザー FromBooska
提出日時 2023-03-20 14:05:30
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,139 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 272 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 79,616 KB
最終ジャッジ日時 2024-09-18 14:03:53
合計ジャッジ時間 8,789 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other TLE * 1 -- * 36
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# 約数の個数は素因数の乗数+1の積
# ということはその数に存在しない素因数倍であれば約数個数は2倍になる
# たとえば12であれば2と3は素数なので5倍の60のときに約数個数は2倍になる
# 存在しない素因数前に、存在する素因数の乗数+1を2倍にできる場合はそれでもok
# たとえば6=2**1*3**1で、4をかければ2**3となり約数個数は2倍になる
# 2*3*5*7*11*13*17*19*23*29*31 > 10**11なので、ここまでの素因数で存在しないものがあるはず
# 面倒なのは420=2**2*3*5*7, この倍数は6すると2と3の乗数が増えて倍になる
# そうであれば31までで全探索した方が早いか

# 約数個数def
def divisor_count(n):
    count = 0
    i = 1
    while i*i <= n:
        if n % i == 0:
            count += 1
            if i != n // i:
                count += 1
        i += 1
    return count

T = int(input())
for t in range(T):
    X = int(input())
    X_count = divisor_count(X)
    for m in range(2, 32):
        if divisor_count(X*m) == X_count*2:
            print(X*m)
            break
0