こんにちは、ナナオです。
前回に引き続き競プロを実施していきたいと思います。
今回の問題は以下です。
実装
正方形にするという要件がそもそも結構むずい気がするんですが、本当に星2か？
まず、a = b = cの場合は0回でいいです。
また、2 1 1や1 2 1の場合は1回でいいです。
3 1 1の場合は2回です。4 1 1の場合は3回です。4 2 2の場合は1回です。
というように、二辺が同じ場合は公約数に沿った法則性がありそうですね。
つまり、「（abcの最大）/（abcの公約数）-（abcの最小）/（abcの公約数）」みたいな…
三辺とも違う場合はどうでしょうか？
9 6 3の場合、333にすればいいですね。
イメージがつかなかったのでちょっと図を描いてみました。
…図に書いてみたらわかりました。3回切る必要があります。
二辺が同じ場合の法則を適用すると「3 - 1 = 2」になるので、3辺になるとちょっと法則が変わるっぽい…？
ここで問題の例を見ると、3 2 2の場合は4回切る必要があるようですね。となると先ほど私が立てた法則も間違っていることがわかりますね。これもうわかんねぇなぁ…
ただ、公約数が絡んでいそうなことはわかります。
3 2 2の場合の公約数は1で4回切る必要がある…ということで、以下のような方程式ならどうでしょうか？
a / (abcの公約数) - 1 + b / (abcの公約数) - 1 + c / (abcの公約数) - 1
これならすべてのユースケースに合っていそうですね。
ということで実装していきます。
ポイントは公約数を出力する実装です。
use proconio::input;
fn gcd(a: u32, b: u32, c: u32) -> u32 {
let min = a.min(b).min(c);
for i in (1..=min).rev() {
if a % i == 0 && b % i == 0 && c % i == 0 {
return i;
}
}
1
}
fn main() {
input! {
a: u32,
b: u32,
c: u32,
}
let gcd = gcd(a, b, c);
let r = a / gcd - 1 + b / gcd - 1 + c / gcd - 1;
println!("{}", r);
}
オーバーフローしてしまったので、数値型をより余裕のある形に変更しました。
use proconio::input;
fn gcd(a: u64, b: u64, c: u64) -> u64 {
let min = a.min(b).min(c);
for i in (1..=min).rev() {
if a % i == 0 && b % i == 0 && c % i == 0 {
return i;
}
}
1
}
fn main() {
input! {
a: u64,
b: u64,
c: u64,
}
let gcd = gcd(a, b, c);
let r = a / gcd - 1 + b / gcd - 1 + c / gcd - 1;
println!("{}", r);
}
ただ、これでもTLEになってしまいます。。
桁数が大きいので、gcdの求め方がもっと効率的じゃないとだめっぽいですね。
ちょっとAIと壁打ちします。
…ということで壁打ちしてきました。
公約数を出すのはユークリッドの互除法を使うのが一般的なようです。
なんか前も使ったような…
と思ったらやっぱり使っていました。
全然覚えていませんでした。
このアルゴリズムの核心は、**「大きい方を、小さい方で割った『余り』に置き換えても、公約数は変わらない」**という性質です。
ということで以下のように修正しました。
use proconio::input;
fn gcd(mut a: u64, mut b: u64) -> u64 {
while b != 0 {
a %= b;
std::mem::swap(&mut a, &mut b);
}
a
}
fn main() {
input! {
a: u64,
b: u64,
c: u64,
}
let gcd = gcd(gcd(a, b), c);
let r = a / gcd - 1 + b / gcd - 1 + c / gcd - 1;
println!("{}", r);
}
これで通りました！
もっとユークリッドの互除法を使った問題を解かないとな…と感じました。
それでは今回はこれで👍