自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 22:21:29，当前版本为作者最后更新于2020-05-04 13:42:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

附：方程化简那块LaTeX炸了……但在博客里显示的是正常的，我也不知道为啥……还请大家多多包容/kel，您如果有需要可以移步博客，感谢谅解！

以下是原文：

---

考场上花了2h才推出式子，我太菜了/kel

一.前置知识：

令$\lfloor a \rfloor$表示对$a$向下取整，$\lceil a \rceil$表示对$a$向上取整。则有：

• 对于一个小数部分不为0的浮点数$a$，若$a$的整数部分为$k$，则$\lfloor a \rfloor=k$，$\lceil a \rceil=k+1$。
• 对于一个小数部分等于0的浮点数$a$，$\lfloor a \rfloor=\lceil a \rceil=a$
• 对于一个浮点数$a$，若$\lfloor a \rfloor=k$，那么a的取值范围为$k\le a <k+1$，若$\lceil a \rceil=k$，那么a的取值为$k-1<a\le k$

二.推导式子

题目的要求是求出方程$\lfloor \frac{i}{j}\rfloor+\lceil \frac{j}{i} \rceil=m$且$i+j=n$的正整数解的个数。

那好办，把这个方程转化成不等式不就行了。

第一个方程有两个变化量：$\lfloor \frac{i}{j}\rfloor$和$\lceil \frac{j}{i} \rceil$，它们之间的关系并不明朗。如果能把两个化简成一个那该多好啊。

如何化简呢？不难发现$i<j$时$\lfloor \frac{i}{j} \rfloor=0$，而$i\ge j$时$\lceil \frac{j}{i}\rceil=1$。也就是说不管$i,j$谁大谁小，总是有一个变化量的值是可以确定的。因此这个方程就愉快地化简成了：

$$\begin{cases} 0+\lceil\frac{j}{i}\rceil=m&(i<j)\\ \lfloor\frac{i}{j}\rfloor+1=m&(i\ge j) \end{cases} $$

至此，我们的任务就是求解$\lceil \frac{j}{i} \rceil=m$和$\lfloor \frac{i}{j}\rfloor=m-1$

根据前置知识中的第3条，$\lceil \frac{j}{i} \rceil=m$可转化为不等式$m-1<\frac{j}{i}\le m$，把$i$用$n-j$代替，解出来就是$\frac{n}{m+1}\le i<\frac{n}{m}$，由于$i$是正整数，所以这个不等式等价于$\lceil\frac{n}{m+1}\rceil\le i<\lceil\frac{n}{m}\rceil$，故方程的正整数解有$\lceil\frac{n}{m}\rceil-\lceil\frac{n}{m+1}\rceil$个

同理，另一个方程$\lfloor \frac{i}{j}\rfloor=m-1$通过上述做法可以得出正整数解有$\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m+1}\rfloor$个

（就只是变了一下数值和取整的方向，不再赘述qwq）

综上，对于每组$n,m$，其答案为$\lceil\frac{n}{m}\rceil-\lceil\frac{n}{m+1}\rceil+\lfloor\frac{n}{m}\rfloor-\lfloor\frac{n}{m+1}\rfloor$。

最后特判一下特殊情况，直接输出，这题就做完了。

三.代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)//宏定义简化for循环 
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){//快读 
	int x=0,fh=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	return x*fh;
}

void work(){//求解 
	int n=read(),m=read(),ans=0;
	//很好想的特判不多说 
	if(m>n||m==1){
		puts("0");
		return;
	} 
	if(m==n-1||m==n){
		puts("1");
		return;
	}
	int x,y;//取值范围 
	x=ceil(n*1.0/(m+1)),y=ceil(n*1.0/m);//化简后得到的第一个不等式 
	ans+=y-x;
	x=floor(n*1.0/(m+1)),y=floor(n*1.0/m);//化简后得到的第二个不等式 
	ans+=y-x;
	printf("%d\n",ans);
	return;
}

int main(){
	int T=read(); 
	while(T--) work();
	return 0;
}

码LaTeX不易，如果这篇文章给予了您帮助，您看能不能点个赞再走？谢谢！