085 - Multiplication 085（★4）
キーワード
解説
制約
より, を満たす全ての を調べるのは不可能.
題意を満たす時, は の約数となるため, K の約数についてのみ調べればよい. 全ての約数の列挙は, で可能.
💡
枝刈り全探索でも可能
という条件から, 少なくとも が言える.
あるいは となった時点で打ち切る.
についてはループを回さず, が で割り切れるかつ を満たせばansをインクリメントする.
提出コード
約数のみ:
func main() {
var k int
scanIntVariables(&k)
divisors := make([]int, 0)
for i := 1; i <= k; i++ {
if i*i > k {
break
}
if k%i == 0 {
divisors = append(divisors, i)
}
}
ans := 0
for i := 0 ;i<len(divisors);i++{
a := divisors[i]
if a * a > k{
break
}
for j := i;j<len(divisors);j++{
b := divisors[j]
if a * b * b > k{
break
}
if k%(a*b) == 0 && k/(a*b) >= b{
ans++
}
}
}
writeLine(ans)
}枝刈り全探索:
func main() {
var k int
scanIntVariables(&k)
ans := 0
for a:=1;a <= k; a++ {
if a * a * a > k {
break
}
for b:=a;b <= k; b++ {
if a * b * b > k {
break
}
if k % (a * b) == 0 && k / (a * b) >= b {
ans++
}
}
}
writeLine(ans)
}