D - Product of Divisors

2 secs 1024 MB
bayashiko's icon bayashiko

aa の正の約数の総積は、 aa の約数の個数を bb として、ab/2a^{b/2} です。
よって、 ab/2=Xa^{b/2}=X となるような aa のうち最小のものを見つければ良いです。
両辺2乗して、 ab=X2a^b=X^2 とします。
あとは、X2X^2xyx^y と表した時、 xx の約数が yy 個であるかという判定を全部試せば良いです。
xyx^yyy の値の候補としてあり得るものは、 X2X^2 を素因数分解して現れた各素因数の肩の値の公約数です。
(X=1X=1 のケースに注意する必要があります)