問題
ポイント
a,b,cの候補を全探索していきますが、実直に全てのパターンを試すとTLEとなってしまいます。
そこで、問題文から得られるaは√k以下、bはa以上という制約を利用して全探索の範囲を絞ることで時間内に探索を終えることができます。
以上を踏まえ、実装したコードがこちらです。
コード
def main():
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
K = int(input())
# aとbの候補を格納する
divisors = set()
for d1 in range(1, int(K**0.5)+1): # aは√k以下
if K % d1 != 0:
continue
else:
divisors.add(d1) # a
divisors.add(K // d1) # b
ans = 0
divisors = sorted(divisors) # a<=b<=cの制約があるため一度ソートする
# 条件を満たすa,b,cを探索する
for i in range(len(divisors)):
for j in range(i, len(divisors)): # bはa以上
a = divisors[i]
b = divisors[j]
if K % (a * b) != 0: # a*bで割り切れなければ次のループ
continue
else:
c = K // (a * b)
if a <= b <= c:
ans += 1
print(ans)
if __name__ == '__main__':
main()
