Namaran

Code daily. Without assist.

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 を組み立てても同じ結果になります。