【题解】CF1485C Floor and Mod（二分答案，整除分块）

【题解】CF1485C Floor and Mod

emmm……NOIP 考前两周，跟 CSP 考前一样(虽然最后并没有去考)，写篇题解增加以下 RP(雾)。

提供一篇思路大体和题解区相同但用了二分写法的题解。

题目链接

CF1485C Floor and Mod

题意概述

求 1≤a≤x,1≤b≤y" role="presentation">1≤a≤x,1≤b≤y$1\le a\le x,1\le b\le y$ 且 ⌊ab⌋=amodb" role="presentation">⌊ab⌋=amodb$\lfloor \frac{a}{b}\rfloor =amodb$ 的 (a,b)" role="presentation">(a,b)$(a,b)$ 个数。

数据范围

• 1≤x,y≤109" role="presentation">1≤x,y≤109$1\le x,y\le {10}^9$

思路分析

首先我们设 ⌊ab⌋=k" role="presentation">⌊ab⌋=k$\lfloor {\displaystyle \frac{a}{b}}\rfloor =k$，则：a=bk+k=k(b+1)" role="presentation">a=bk+k=k(b+1)$a=bk+k=k(b+1)$。也就是说 a" role="presentation">a$a$ 是 b+1" role="presentation">b+1$b+1$ 的倍数。

那么题意转化为：

在 [1,x]" role="presentation">[1,x]$[1,x]$ 里找一个 a" role="presentation">a$a$，在 [1,y]" role="presentation">[1,y]$[1,y]$ 里找一个 b" role="presentation">b$b$，满足 a" role="presentation">a$a$ 是 b+1" role="presentation">b+1$b+1$ 的倍数，问有多少对这样的 (a,b)" role="presentation">(a,b)$(a,b)$。

那么我们考虑对于 [1,y]" role="presentation">[1,y]$[1,y]$ 里的每一个 b" role="presentation">b$b$，[1,x]" role="presentation">[1,x]$[1,x]$ 中有多少个 a" role="presentation">a$a$ 满足题意。其实就相当于问 [1,x]" role="presentation">[1,x]$[1,x]$ 中有多少个 b+1" role="presentation">b+1$b+1$ 的倍数，显然有 ⌊xb+1⌋" role="presentation">⌊xb+1⌋$\lfloor {\displaystyle \frac{x}{b+1}}\rfloor$ 个。

那么总的答案就为

∑i=1y⌊xi+1⌋=∑i=2y+1⌊xi⌋" role="presentation">∑i=1y⌊xi+1⌋=∑i=2y+1⌊xi⌋$$\sum _{i=1}^y\lfloor \frac{x}{i+1}\rfloor =\sum _{i=2}^{y+1}\lfloor \frac{x}{i}\rfloor$$

那么可以直接整除分块解决。

结果我写完发现样例都过不了。。所以显然是有问题的。

我们发现 b" role="presentation">b$b$ 首先不能为 1" role="presentation">1$1$，因为任何数是 1" role="presentation">1$1$ 的倍数，而任何数除以 1" role="presentation">1$1$ 不可能为 0" role="presentation">0$0$。

所以我们的下界应该从 3" role="presentation">3$3$ 开始。

其次，在 a=bk+k=k(b+1)" role="presentation">a=bk+k=k(b+1)$a=bk+k=k(b+1)$ 中，我们忽略了一个重要条件，k" role="presentation">k$k$ 在这里相当于 amodb" role="presentation">amodb$amodb$，是余数，而余数不能大于等于除数，即 k<b" role="presentation">k<b$k<b$。

所以对于 [3,y]" role="presentation">[3,y]$[3,y]$ 的每一个 b" role="presentation">b$b$，其实只有 ⌊ab+1⌋<b" role="presentation">⌊ab+1⌋<b$\lfloor {\displaystyle \frac{a}{b+1}}\rfloor <b$ 的 a" role="presentation">a$a$ 才满足题意。

那么这样的 a" role="presentation">a$a$ 在 [1,x]" role="presentation">[1,x]$[1,x]$ 中有 ⌊min(b+1)(b−1),xb+1⌋" role="presentation">⌊min(b+1)(b−1),xb+1⌋$\lfloor {\displaystyle \frac{min(b+1)(b-1),x}{b+1}}\rfloor$ 个。

那么整个答案就为：

∑i=2y⌊min((i+1)(i−1),x)i+1⌋=∑i=3y+1⌊min(i(i−2),x)i⌋=∑i=3lim(i−2)+∑i=lim+1y+1⌊xi⌋=(1+lim−2)×(lim−3+1)2+∑i=lim+1y+1⌊xi⌋" role="presentation">∑i=2y⌊min((i+1)(i−1),x)i+1⌋=∑i=3y+1⌊min(i(i−2),x)i⌋=∑i=3lim(i−2)+∑i=lim+1y+1⌊xi⌋=(1+lim−2)×(lim−3+1)2+∑i=lim+1y+1⌊xi⌋$$\begin{array}{rl}\sum _{i=2}^y\lfloor {\displaystyle \frac{min((i+1)(i-1),x)}{i+1}}\rfloor & =\sum _{i=3}^{y+1}\lfloor {\displaystyle \frac{min(i(i-2),x)}{i}}\rfloor \\ & =\sum _{i=3}^{lim}(i-2)+\sum _{i=lim+1}^{y+1}\lfloor {\displaystyle \frac{x}{i}}\rfloor \\ & =\frac{(1+lim-2)\times (lim-3+1)}{2}+\sum _{i=lim+1}^{y+1}\lfloor {\displaystyle \frac{x}{i}}\rfloor \end{array}$$

其中 lim" role="presentation">lim$lim$ 表示的是使得 i×(i−2)≤x" role="presentation">i×(i−2)≤x$i\times (i-2)\le x$ 的最后一个 i" role="presentation">i$i$。

那么 lim" role="presentation">lim$lim$ 直接枚举/解不等式/二分都可，我这里采用的是二分。

最后的式子中，第一项显然可以 O(1)" role="presentation">O(1)$O(1)$ 求出，第二项显然可以整除分块，于是整道题成功解决。

时间复杂度：O(T(log⁡y+y))" role="presentation">O(T(logy+y√))$O(T(\log y+\sqrt{y}))$。

易错点

没啥细节，只是需要开 long long。

代码实现

//CF1485C
#include
#include
#include
#define int long long
using namespace std;
 
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
 
int work(int n,int k,int lim)
{
	int ret=0;
	for(int l=lim,r;l<=n;l=r+1)
	{
		if(k/l==0)break;
		r=min(k/(k/l),n);
		ret+=(k/l)*(r-l+1);
	}
	return ret;
}
 
signed main()
{
	int T;
	T=read();
	while(T--)
	{
		int x,y;
		x=read();y=read();
		int now=0;
		for(int step=(1ll<<30);step>=1;step>>=1)
		{
			if(now+step<=(y+1)&&(now+step)*(now+step-2)<=x)now+=step;
		}
		int lim=now;
		cout<<(lim-2)*(lim-1)/2+work(y+1,x,lim+1)<<'\n';
	}
}