4s, 512M
题目描述
Alice 和 Bob 在打乒乓球,乒乓球比赛的规则是这样的:一场比赛中两位选手将进行若干局比赛,选手只需要赢得 \(X\) 局比赛就宣告其胜利;每局比赛中两位选手将进行若干盘比赛,选手只需要赢得 \(Y\) 盘比赛就宣告其胜利;每盘比赛中两位选手将进行乒乓球对决,有且仅有一位选手能被宣告胜利。
你作为 Alice 的朋友观战了他们的比赛,发现 Alice 赢了 \(P\) 盘比赛,Bob 赢了 \(Q\) 盘比赛,最后 Alice 取得了整场比赛的胜利。但是你已经忘了 \(X, Y\) 的具体取值,请问有多少种 \(X, Y\) 使得能存在一种方案满足你记录下的信息。
输入格式
第一行两个正整数 \(P, Q\)。
输出格式
第一行一个正整数表示方案数。
样例
7 5
4
样例零中,\((X, Y)\) 的所有可能取值为 \((1, 7), (2, 3), (3, 2), (7, 1)\)。
554 454
1226
数据范围
- 对于 \(30\%\) 的数据,\(P, Q\leq 10^3\)。
- 对于 \(50\%\) 的数据,\(P, Q\leq 10^6\)。
- 对于 \(70\%\) 的数据,\(P, Q\leq 10^{12}\)。
- 另外有 \(10\%\) 的数据,\(Q=0\)。
- 对于 \(100\%\) 的数据,\(P, Q\leq 10^{14}\),并请注意 \(X, Y\) 均应为正整数。
solution
设 Bob 赢下了 \(Z\) 局比赛,因为 Bob 赢的局数会影响 Alice 可以赢的局数。可以列出以下不等式:
\[\begin{aligned} Z&<X\\ XY&\leq P\leq XY+Z(Y-1)\\ ZY&\leq Q\leq ZY+X(Y-1) \end{aligned} \]观察到在 \(ZY\leq Q\) 的限制下,将 \(Z\) 增大一定是不劣的,所以一定有
\[Z=\min(X - 1, \left\lfloor Q/Y\right\rfloor) \]因为 \(XY\leq P\),所以可以调和级数枚举 \(X, Y\),获得 \(50\) 分。
对 \(Z\) 的取值分类讨论。
Z = floor(Q / Y)
对于 \(ZY\leq Q\leq ZY+X(Y-1)\),这自然满足,因为 \(Q-ZY<Y\),所以 \(Q-ZY\leq Y - 1\leq X(Y - 1)\)。
对于 \(XY\leq P\leq XY+Z(Y-1)=XY+ZY-Z\) 以及 \(Z\leq X-1\) 可以写出:
\[\max(Z+1, \left\lceil(P+Z)/Y\right\rceil-Z)\leq X\leq \left\lfloor P/Y\right\rfloor \]三次整除分块解决。先 \(\left\lfloor Q/Y\right\rfloor\) 确定 \(Z\) 以及 \(Y\) 对应区间。然后获得 $ \left\lceil(P+Z)/Y\right\rceil$(注意向上取整,或者写为 $ \left\lfloor(P+Z-1)/Y\right\rfloor+1$)以及 $ \left\lfloor P/Y\right\rfloor$。
Z = X - 1
对于 \(X-1<\left\lfloor Q/Y\right\rfloor\) (等号在上一种情况讨论了)可以推出 \(X\leq Q/Y\) 所以 \(XY\leq Q\)。
对于 \(ZY\leq Q\leq ZY+X(Y-1)\),左边自然满足,右边 \(Q\leq 2XY-X-Y\)。
对于 \(XY\leq P\leq XY+Z(Y-1)=2XY-X-Y+1\),其实发现两条不等式很类似。感受一下:
\[\begin{aligned} &XY\leq P\leq 2XY-X-Y+1\\ &XY\leq Q\leq 2XY-X-Y\\ \end{aligned} \]两个变量的地位等同,不妨:
\[X\leq\left\lfloor\min(P, Q)/Y\right\rfloor \]后面这个部分,\(P, Q\) 对称,设 \(R=\max(P - 1, Q)\),然后
\[R\leq 2XY-X-Y \]以 \(X\) 为主元,求出 \(X\) 的范围。
\[R+Y\leq (2Y-1)X \]所以
\[X\geq\left\lceil \frac{R+Y}{2Y-1}\right\rceil \]即
\[X\geq\left\lfloor \frac{R+Y-1}{2Y-1}\right\rfloor+1 \]感受一下,右边的值域比较小,尝试对 \(Y\) 进一步整除分块。令 \(V=\left\lfloor\frac{R+Y-1}{2Y-1}\right\rfloor\)。求出使得那一坨东西 \(=V\) 的 \(Y\) 的范围。
\[\begin{aligned} V&\leq (R+Y-1)/(2Y-1)\\ 2VY-V&\leq R+Y-1\\ Y&\leq \frac{R+V-1}{2V-1}\\ Y&\leq \left\lfloor\frac{R+V-1}{2V-1}\right\rfloor\\ \end{aligned} \]至此所有问题都解决了。时间复杂度 \(O(\sqrt P+\sqrt Q)\),具体几倍常数不知道。
code
正确性未知
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
LL p, q, ret;
int main() {
#ifndef LOCAL
cin.tie(nullptr)->sync_with_stdio(false);
#endif
cin >> p >> q;
for (LL l = 1, r; l <= p; l = r + 1) {
LL z = q / l, pz1 = p + z - 1;
r = p / (p / l);
if (l <= pz1) r = min(r, pz1 / (pz1 / l));
if (z) r = min(r, q / z);
ret += (r - l + 1) * max(0ll, p / l - max(z + 1, pz1 / l + 1 - z) + 1);
}
for (LL l = 1, r; l <= min(p, q); l = r + 1) {
r = min(p, q) / (min(p, q) / l);
LL v = (max(p - 1, q) + l - 1) / (2 * l - 1);
if (v) r = min(r, (max(p - 1, q) + v - 1) / (2 * v - 1));
ret += (r - l + 1) * max(0ll, min(p, q) / l - v);
}
cout << ret << endl;
return 0;
}