给定 $n,m$ 求满足 $i+j=n$ 且 $\lfloor i/j\rfloor+\lceil j/i\rceil=m$ 的正整数对 $(i,j)$ 的对数。

有 $10^5$ 组数据。$n,m\leq 10^7$ 。

将 $j=n-i$ 带入第二个式子后发现是先减后增的。在极值点两侧分别二分即可。

或者分别讨论 $i<j$ 以及 $i\geq j$ 的情况，最后推出式子 $\lfloor \frac{n-1}{m} \rfloor-\lfloor \frac{n-1}{m+1}\rfloor+\lfloor \frac{n}{m} \rfloor-\lfloor \frac{n}{m+1} \rfloor$ 。

给定一个 $n$ 个点 $m$ 条边的边带权无向图，在 $0$ 时刻你在点 $1$ 上。

假设当前是 $t$ 时刻，你在点 $v$ 上，你可以选择两种操作：

• 仍停留在点 $v$ 上，操作后到 $t+1$ 时刻。
• 选择一条边 $(a,b,w)$ 满足 $a=v$ 或 $b=v$ ，则你到这条边连接的另一个点上，操作后到 $t+w$ 时刻。

有 $k$ 条信息，$(t_i,v_i)$ 表示在 $t_i$ 时刻，点 $v_i$ 上会出现一只猪。如果这是你在这个点上，则你抓到了这只猪。

求最多能抓多少只猪。$n\leq 200$ ，$k\leq 5000$ ，$t\leq 10^9$ 。

感觉和这个题好像。

先跑一遍 floyd。

对时间排序。设 $f[i]$ 表示考虑前 $i$ 条信息最多抓到的数量。枚举之后的信息判断转移即可。时间复杂度 $O(n^3+k^2)$。

可以做一个小的优化。枚举之后的信息可以改为枚举点对应的信息，复杂度是 $O(n^3+n\times k)$ 。