2026-10-20
simplify_sqrt.rs
fn simplify_sqrt(mut n: u64) -> (u64, u64) {
}
1より大きい平方数で割り切れない正の整数を、平方因子をもたない数(squarefree integer)といいます。正の整数 n に対し、n == a * a * b を満たし、b が平方因子をもたない数であるような組 (a, b) を返す simplify_sqrt を書いてください。√n を a√b の形に直したときの a と b にあたり、この組はただ1つに決まります。n は1以上10の12乗以下とし、n が1なら (1, 1) です。
入力例 1
simplify_sqrt(360)
出力例 1
(6, 10)
入力例 2
simplify_sqrt(98)
出力例 2
(7, 2)
入力例 3
simplify_sqrt(1)
出力例 3
(1, 1)
Reference
fn simplify_sqrt(mut n: u64) -> (u64, u64) {
let (mut outside, mut inside) = (1, 1);
let mut p = 2;
while p * p <= n {
while n.is_multiple_of(p * p) {
n /= p * p;
outside *= p;
}
if n.is_multiple_of(p) {
n /= p;
inside *= p;
}
p += 1;
}
(outside, inside * n)
}
p を2から順に試し、n が p * p で割り切れるあいだは割って p を根号の外に出し、そのあと p でまだ割り切れれば、その1個を根号の中に残します。素因数 p の指数が e なら、外に出る p の個数は e を2で割った商、中に残る個数は余りの0か1です。360 = 2³ × 3² × 5 では、2が外と中に1個ずつ、3が外に1個出ます。
ループは p * p <= n のあいだだけ回るので、抜けたあとに1より大きい n が残ることがあります。この n は p 未満の素因数をもたず、しかも p * p より小さいので素数です。指数が1の素因数として、根号の中に掛けます。入力例 1 の5はこの形で残り、最後を inside * n ではなく inside にすると (6, 2) が返って5が消えます。
p が4や6のような合成数のときに割り切れることはありません。p より小さい素因数は、その時点で n からすべて取り除かれているからです。n が10の12乗以下なら、p は10の6乗を少し超えるところまでしか進まず、p * p も u64 に収まります。
掲載したのは参考実装で、唯一の正解ではありません。先に素因数と指数の組をすべて求め、指数を2で割った商と余りから a と b を組み立てても同じ結果になります。