自动搬运

查看原文

来自洛谷，原作者为

	zeroflows 白六的忠实粉丝（要互关的宝宝记得私信）

搬运于2025-08-24 22:51:51，当前版本为作者最后更新于2024-08-21 16:02:04，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

首先我们看下数据范围，$n \le 3000$，范围很小，所以暴力枚举。
于是第一份代码出来了。

#include<bits/stdc++.h>
using namespace std;
int s,a,b,c,d,n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(),cout.tie();
	cin>>n>>m;
	for(a=1;a<=n;a++)
	{
		for(b=1;b<=n;b++)
		{
			for(c=1;c<a;c++)
			{
				for(d=1;d<b;d++)
				{
					if(a==m||b==m)
						continue;
					if(a*b-c*d==n)
						s++;
				}
			}
		}
	}
	cout<<s;
}

但只有 37 分。

然后考虑优化。
题目最主要的条件是 $a \times b - c \times d = n$ 变下形可得 $n + c \times d = a \times b$，再考虑下范围。
于是第二份代码出来了。

#include<bits/stdc++.h>
using namespace std;
int s,a,b,c,d,n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(),cout.tie();
	cin>>n>>m;
	for(c=n-2;c>=1;c--)
	{
		for(d=n-c;d>=1;d--)
		{
			for(a=n-1;a>c;a--)
			{
				if((n+d*c)%a||(n+d*c)/a<=d)
					continue;
				b=(n+d*c)/a;
				if(a!=m&&b!=m&&a*b-c*d==n)
					s++;
			}
		}
	}
	cout<<s;
}

但这样写也只有 51 分。

那我们换一种思路。
因为 $a$ 与 $b$ 不能等于 $m$ 所以我们放在前面，减少循环次数。
我们考虑一下 $a \times b$ 的大小。

• 首先 $a \times b - c \times d = n$，所以 $a \times b$ 小于 $n$ 的话直接往下走。
  另外考虑一下 $a$ 与 $b$ 的大小关系。
  我们枚举一下，可以发现 $a$ 与 $b$ 的值总是在 $1 \sim n$ 之间。而且当 $a \ne b$ 时，a b c d 与 b a c d 两个顺序都成立，同时 c 的最小值为 $\max ( 1 , ( a \times b - n ) \div b)$，于是我们可以这样。

for(a=1;a<=n;a++)
	{
		if(a==m)
			continue;
		for(b=a;b<=n;b++)
		{
			if(b==m||a*b<=n)
				continue;
			for(c=max(1,(a*b-n)/b);c<a;c++)
			{
			}
		}
	}

最后结合题目要求判断就行了。

代码

#include<bits/stdc++.h>
using namespace std;
int s,a,b,c,d,n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(),cout.tie();
	cin>>n>>m;
	for(a=1;a<=n;a++)
	{
		if(a==m)
			continue;
		for(b=a;b<=n;b++)
		{
			if(b==m||a*b<=n)
				continue;
			for(c=max(1,(a*b-n)/b);c<a;c++)
			{
				d=a*b-n;
				if(d%c!=0||d/c>=b)
					continue;
				s++;
				if(a!=b)
					s++;
			}
		}
	}
	cout<<s;
}