長方形in直角三角形

2 secs 1024 MB

shinnshinn

Problem

Submissions

Test cases

Editorial

解説

右側から長方形を敷き詰めるのが最適です。なぜなら左側に寄ると三角形の斜辺で高さが低くなるからです。

$[x,x+1]$ に正方形を縦に積められる個数は $\left\lfloor \frac{Y}{X}x / H \right\rfloor$ 個と求めることができます。

よって、以下の式をFloor Sumで求めれば良いです。

\sum_{i=0}^{X-1}\left\lfloor \frac{Y\times i}{X H}\right\rfloor

実装

xxxxxxxxxx
 
use proconio::*;
​
// \sum_{i = 0}^{n-1} floor(\frac{a \times i + b}{m})
fn floor_sum(n: i64, m: i64, mut a: i64, mut b: i64) -> i64 {
    let mut ans = 0;
    if a >= m {
        ans += a/m * ((n-1)*n/2);
        a %= m;
    }
    if b >= m {
        ans += b/m * n;
        b %= m;
    }
​
    let y_max = (a*n + b) / m;
    let x_max = m*y_max - b;
​
    if y_max == 0 { return ans; }
​
    ans += (n - (x_max + a-1)/a) * y_max;
    ans += floor_sum(y_max, a, m, (a - x_max%a)%a);
​
    ans
}
​
fn main() {
    input! {
        t: usize,
    }
    for _ in 0..t {
        input! {
            x: i64, 
            y: i64,
            h: i64,
        }
​
        let ans = floor_sum(x, h*x, y, 0);
        println!("{}", ans);
    }
}
​