整数Nが与えられる。
A <= B <= C && A * B * C == N となる A, B, Cの組み合わせの数を求めよ。
解き方
A, B, C はそれぞれ Nの約数であることは分かる。
Nの制約は 10 ** 12 で約数の数はどれくらいか見積もるには、高度合成数 を知っていれば分かる。
高度合成数とは、自分以下の整数の中で約数の数が最も多いものである。
(例えば12は約数が多いことで知られる。)
アルゴ式のサイトによると、1124388064800 の約数は 6912。
A, B が決まればCは自ずと決まるので約 7000 * 7000 の2重ループでA, B, Cの組み合わせを求められる。
func solve() {
n := getInt()
dividors := getDividors(n)
ans := 0
for i := 0; i < len(dividors); i++ {
a := dividors[i]
// overflow対策
if a * a > n {
break
}
for j := i; j < len(dividors); j++ {
b := dividors[j]
// overflow対策
if a * b * b > n {
break
}
if n % (a * b) == 0 && n / (a * b) >= b {
ans++
}
}
}
fmt.Println(ans)
}
https://atcoder.jp/contests/typical90/tasks/typical90_cg
問題概要
整数Nが与えられる。
A <= B <= C && A * B * C == Nとなる A, B, Cの組み合わせの数を求めよ。解き方
A, B, C はそれぞれ Nの約数であることは分かる。 Nの制約は
10 ** 12で約数の数はどれくらいか見積もるには、高度合成数 を知っていれば分かる。 高度合成数とは、自分以下の整数の中で約数の数が最も多いものである。 (例えば12は約数が多いことで知られる。) アルゴ式のサイトによると、1124388064800の約数は 6912。A, B が決まればCは自ずと決まるので約 7000 * 7000 の2重ループでA, B, Cの組み合わせを求められる。
https://atcoder.jp/contests/typical90/submissions/53268772