考场上切了，但是比较神奇的题，应该是蓝/紫。
Discription
乒乓球 \(\text{ }\)时间限制：\(\bold{3}\) 秒
众所周知，一场乒乓球比赛共有两个玩家 \(A\) 和 \(B\) 参与，其中一场比赛由多局比赛组成，而每局比赛中又由多盘比赛组成。
每盘比赛 \(A\) 或 \(B\) 只有一名选手获胜。当其中一名选手在一局比赛中达到 \(X\) 盘比赛胜利时，该局比赛结束，并且该名选手被宣布为这局比赛的获胜者。
类似的，当其中一名选手在 \(Y\) 局比赛中获得胜利时，该名选手被称为该场游戏的获胜者。
你刚刚看了一场比赛，其中 \(A\) 获得了 \(P\) 盘比赛的胜利，B 获得了 \(Q\) 盘比赛的胜利，并且你知道 \(A\) 是该场比赛的获胜者，但你忘记了 \(X\) 和 \(Y\) 的具体数值。
你想知道有多少对可能的 \((X,Y)\)，使得至少存在一组合法的获胜情况满足要求。
数据范围：\(0 \le P,Q \le 10^{14}\)。
Analysis
这个神奇的数据范围，加上计数，不难想到正解为整除分块，往这个方面想。
设 \(B\) 赢了 \(k\) 场，不难列出不等式组：
\[\begin{cases} k \lt y & \textcircled{\small{1}}\\ xy \le p \le xy+k(x-1) & \textcircled{\small{2}}\\ kx \le q \le kx+y(x-1) & \textcircled{\small{3}} \end{cases}\]由 \(\textcircled{\small{1}}\) 和 \(\textcircled{\small{3}}\) 中 \(q\) 的下界知：
\[k \le \min(y-1,\lfloor\frac{q}{x}\rfloor)\text{ }\textcircled{\small{4}} \]这时候需要一点感性理解：
- 当 \(\textcircled{\small{4}}\) 时，\(\textcircled{\small{1}}\) 和 \(\textcircled{\small{3}}\) 中 \(q\) 的下界一定成立；
- 对于越大的 \(k\)，\(\textcircled{\small{2}}\) 的下界不变，上界增大；
- \(\textcircled{\small{3}}\) 中区间长度与 \(k\) 无关，所以下界在 \(\le q\) 的前提下越大越好。
综上，\(k\) 越大越好，于是钦定：
\[k = \min(y-1,\lfloor\frac{q}{x}\rfloor) \]注意到此时可以调和级数 \(O(p\log p)\) 的枚举 \(x\) 和 \(y\) 同时 \(O(1)\) 检验，期望得分 \(50\) 分。
再想优化，就需要分类讨论：
$\bold{I.} $ 当 \(\lfloor\frac{q}{x}\rfloor \le y-1\) 时，
此时 \(k=\lfloor\frac{q}{x}\rfloor\)。
分析前面的不等式组：
- \(\textcircled{\small{1}}\) 和 \(\textcircled{\small{3}}\) 中 \(q\) 的下界一定成立；
- 对于 \(\textcircled{\small{3}}\) 中 \(q\) 的上界 \(kx+y(x-1)\)，代入 \(k\) 得：
注意到 \(\lfloor\frac{q}{x}\rfloor\cdot x \gt q-x\)，而 \(y \ge 1\) 即 \(y(x-1) \ge x-1\)，于是 \(\textcircled{\small{3}}\) 恒成立。
综上，只需考虑 \(\textcircled{\small{2}}\) 和 \(\lfloor\frac{q}{x}\rfloor \le y-1\) 即 \(k\le y-1\) 的大前提即可。
\[\begin{cases} k \le y-1\\ xy \le p \le xy+k(x-1) & \textcircled{\small{2}}\\ \end{cases}\]考虑卡出 \(y\) 的范围，易得：
\[\max(k+1,\lceil\frac{p+k}{x}\rceil-k)\le y\le \lfloor\frac{p}{x}\rfloor \]改写一下向上取整：
\[\max(k+1,\lfloor\frac{p+k-1}{x}\rfloor+1-k)\le y\le \lfloor\frac{p}{x}\rfloor \]接着考虑怎么整除分块，比较好写的做法是：循环中先以 \(\lfloor\frac{p}{x}\rfloor\) 进行分块，算出 \(k\) 和 \(\lfloor\frac{p+k-1}{x}\rfloor\) 在对右端点 \(r\) 进行更新即可。
先放一下实现：
for(ll l=1,r;l<=p;l=r+1){
r=p/(p/l);
ll k=q/l,tmp=p+k-1;
if(k) r=min(r,q/k);
if(l<=tmp) r=min(r,tmp/(tmp/l));
ans+=(r-l+1)*max(p/l-max(k+1,tmp/l+1-k)+1,0ll);
}
$\bold{II.} $ 当 \(\lfloor\frac{q}{x}\rfloor \gt y-1\) 时，
此时 \(k=y-1\)。
类似的，分析原不等式组：
- \(\textcircled{\small{1}}\) 和 \(\textcircled{\small{3}}\) 中 \(q\) 的下界一定成立；
- 对于 \(\textcircled{\small{2}}\) 中 \(p\) 的下界 \(xy\)，
于是 \(\textcircled{\small{2}}\) 中 \(p\) 的下界的限制必成立；
- 对于 \(\textcircled{\small{3}}\) 中 \(q\) 的下界 \(kx\)，
于是 \(\textcircled{\small{3}}\) 中 \(q\) 的下界的限制必成立；
综上，只需考虑 \(\textcircled{\small{2}}\) 和 \(\textcircled{\small{3}}\) 中的上界。
\(p.s.\) 大前提 \(\lfloor\frac{q}{x}\rfloor \gt y-1\) 在 2. 和 3. 中考虑过了，无需再考虑。
\[\begin{cases} p \le xy+k(x-1) & \textcircled{\small{2}} & (上界)\\ q \le kx+y(x-1) & \textcircled{\small{3}} & (上界) \end{cases}\]将 \(k=y-1\) 代入得：
\[\begin{cases} p \le 2xy-x-y+1 & \textcircled{\small{2}} & (上界)\\ q \le 2xy-x-y & \textcircled{\small{3}} & (上界) \end{cases}\]考虑卡出 \(2xy-x-y\) 的范围，易得：
\[2xy-x-y\ge \max(p-1,q) \]类似的，卡出 \(y\) 的范围，易得：
\[(2x-1)y\ge\max(p-1,q)+x \]\[\implies y \ge\lfloor\frac{x+\max(p-1,q)}{2x-1}\rfloor \]这个就好写很多，直接整除分块即可。
给出实现：
for(ll l=1,r;l<=min(p,q);l=r+1){
r=min(p,q)/(min(p,q)/l);
ll tmp=(max(p-1,q)+l-1)/(2*l-1));
if(tmp) r=min(r,(max(p-1,q)+tmp-1)/(2*tmp-1));
ans+=(r-l+1)*max(min(p,q)/l-tmp,0ll);
}
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p,q,ans;
int main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>p>>q;
for(ll l=1,r;l<=p;l=r+1){
r=p/(p/l);
ll k=q/l,tmp=p+k-1;
if(k) r=min(r,q/k);
if(l<=tmp) r=min(r,tmp/(tmp/l));
ans+=(r-l+1)*max(p/l-max(k+1,tmp/l+1-k)+1,0ll);
}
for(ll l=1,r;l<=min(p,q);l=r+1){
r=min(p,q)/(min(p,q)/l);
ll tmp=(max(p-1,q)+l-1)/(2*l-1);
if(tmp) r=min(r,(max(p-1,q)+tmp-1)/(2*tmp-1));
ans+=(r-l+1)*max(min(p,q)/l-tmp,0ll);
}
cout<<ans<<endl;
return 0;
}