给定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 <bits/stdc++.h> 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; }
原文：http://www.cnblogs.com/BugClearlove/p/4481595.html
