浙江省赛压轴题 Floor Function

给定a,b,c,d, 满足bc>ad, 求使得cn?d?abn?最小的最小的n.

数据规模: 1≤a,b,c,d≤1018

令y=?abx?,x=?bya?, 原问题等价于求cx?dy的最小值, ax≥by,x≥1,y≥0.

分两种情况考虑

1. a≥b

令k=?ab?,y≥kx,c>ad/b≥kd

令a′=a?kb,c′=c?kd,y′=y?kx, 此时原问题的约数条件任然满足, 问题可以缩小规模.

原问题的解(x,y)对应现在的解(x,kx+y′)

显然若a′=0, 我们可以得到(x,y′)=(1,0)

2. a<b

令k=?b?1a?,x>ky

令b′=b?ka,d′=d?k?c,x′=x?ky

类似的, 原问题的约数条件任然满足, 问题可以缩小规模.

显然若d′≤0, 我们可以得到(x′,y)=(1,0)

#include 
using namespace std;
typedef long long LL;

void solve(LL a, LL b, LL c, LL d, LL &x, LL &y) {
  if (a == 0 || d <= 0) {x = 1, y = 0; return;}
  if (a >= b) {
    LL k = a / b;
    solve(a - k * b, b, c - k * d, d, x, y);
    y += k * x;
  }
  else {
    LL k = (b - 1) / a;
    if (d / c < k) x = 1, y = 0;
    else solve(a, b - k * a, c, d - k * c, x, y);
    x += k * y;
  }
}

int main() {
  int T; scanf("%d", &T);
  for (int _ = 0; _ < T; ++ _) {
    LL a, b, c, d; scanf("%lld%lld%lld%lld", &a, &b, &c, &d);
    LL x, y; solve(a, b, c, d, x, y);
    printf("%lld\n", x);
  }
  return 0;
}