怠惰の累積和

技術/競プロ/怪文書/虚無

yukicoder No.300 平方数

問題概要

　整数 $X$ と掛け合わせると平方数になる最小の数を求めよ。

解法

　問題では完成する平方数が $Z$ となっているのでこれを流用する。 $Z$ を素因数分解すると、 $Z=(a_1*a_2*a_3*...*a_n)^2(a$ は $Z$ の素因数の集合 $)$ となる。

　これは $X$ が因数に含まれている数なので、求める数は $X$ を素因数分解した際に、次数が奇数のものをすべてかけたもの( $Z$ の素因数に偶数乗のものがあると平方数にはなりえないので)になる。