D1T1
noip2017最难题。
(O(log)) 做法
要求最大的 (ax+by) ,其中 (x<0) 或 (y<0) 。
已知存在: (ax'+by'=gcd(a,b)=1) 。
考虑已知 (c=ax+by) ,其中 (xgeq 0) 且 (y geq 0) ,则 (c-1=ax+by-1=a(x-x')+b(y-y')) 。
如果 (c-1) 为答案,一定有 (x-x'<0) 或 (y-y'<0) 。
设 (x'_ ext{min}) 为 (ax'+by'=1) 中 (x') 的最小正整数解, (y'_ ext{min}) 为 (ax'+by'=1) 中 (y') 的最小正整数解。
现在令 (x=x'_ ext{min}-1,y=y'_ ext{min}-1) 。
由 (a) 和 (b) 互质和“一定有答案”,可以得到 (a
eq b,a
eq 1,b
eq 1) ,所以 (x'_ ext{min}) 和 (y'_ ext{min}) 不可能都为 (1) ,即 (x) 和 (y) 不可能都为 (0) 。
所以 (ax+by>1) 即 (ax+by-1 > 0) 。
又因为一定有 (x-x'<0) 或 (y-y'<0) ,即 (a(x-x')+b(y-y')=ax+by-1) 是无法准确支付的价值之一。
如果答案不为 (ax+by-1) ,一定存在 (a(x_0-x')+b(y_0-y') > a(x-x')+b(y-y')) 为答案,显然 (x_0 > x) 或 (y_0 > y) ,所以一定有 (x_0 geq x+1 = x'_ ext{min}) 或 (y_0 geq y+1 = y'_ ext{min}) ,则一定存在 (x',y') 使得 (x_0-x'geq 0) 且 (y_0-y' geq 0) ,故不存在 (x_0,y_0) ,所以答案为 (ax+by-1) 。
#include <cstdio>
int a, b;
long long x, y;
void exgcd(int a, int b, long long &x, long long &y) {
if (!b) {
x = 1;
y = 0;
return;
}
exgcd(b, a % b, y, x);
y -= a / b * x;
}
int main() {
scanf("%d%d", &a, &b);
exgcd(a, b, x, y);
x %= b;
if (x <= 0) x += b;
y %= a;
if (y <= 0) y += a;
printf("%lld
", a * (x - 1) + b * (y - 1) - 1);
return 0;
}
(O(1)) 做法
设 (ans = ax + by(0 leq x < b))。(若 (x< 0) 或 (xgeq b),则存在 (0 leq x' < b),使得 (ax equiv ax' pmod b),即 (ax+by = ax'+by')。故表示 (ans) 时可以限制 (0 leq x < b))
若 (ans) 不能被表示出来,则 (y < 0)。
令 (x = b - 1,y = -1),显然 (ans) 最大。
故 (ans = (b-1) imes a+(-1) imes b = ab-a-b)。
D2T3