まずaを決めるとbは M / aで決定できる。
このとき小数点部分がでる場合は切り捨てると a * b < M となるので、M / a は ceilDiv(M, a)、つまり切り上げ除算で求める。
b <= N だったらXになり得るので、それが最小になる場合は答えになる。
これをaが1 ~ Nまで繰り返す。
N <= 10 ** 12なので、最後まで繰り返すとTLEになるが、a * a > Mになったら打ち切りできる。
これは、そこまでいったら a < b となるbを見つけられないため。
ここで打ち切ると計算量がsqrt(10 ** 12) = 10 ** 6 にできて間に合うことがわかる。
func solve() {
in := getInts()
n, m := in[0], in[1]
ans := BIGGEST
for a := 1; a <= n; a++ {
// a*bがm以上になるように、m/aの小数点部分が切り捨てられないようにする
b := ceilDiv(m, a)
if b <= n {
ans = min(ans, a * b)
}
if a * a > m {
break
}
}
if ans == BIGGEST {
fmt.Println(-1)
} else {
fmt.Println(ans)
}
}
https://atcoder.jp/contests/abc296/tasks/abc296_d
問題概要
整数N, Mが与えられる。次の条件を満たす正の整数Xの最小値を求めよ。
制約は、
1 <= N, M <= 10 ** 12入力例
この場合、
7 = 1 * 7で各要素が5以下にならないのでXに採用できない。8 = 2 * 4で各要素が5以下になるのでXに採用できる。解き方
まずaを決めるとbは
M / aで決定できる。 このとき小数点部分がでる場合は切り捨てるとa * b < Mとなるので、M / aはceilDiv(M, a)、つまり切り上げ除算で求める。b <= NだったらXになり得るので、それが最小になる場合は答えになる。 これをaが1 ~ Nまで繰り返す。N <= 10 ** 12なので、最後まで繰り返すとTLEになるが、a * a > Mになったら打ち切りできる。 これは、そこまでいったらa < bとなるbを見つけられないため。 ここで打ち切ると計算量がsqrt(10 ** 12) = 10 ** 6にできて間に合うことがわかる。https://atcoder.jp/contests/abc296/submissions/54184275