专栏文章

题解：P9788 [ROIR 2020] 区域规划 (Day2)

mmairuisheng
P9788题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minkbnxl
此快照首次捕获于
2025/12/02 03:49
3 个月前
此快照最后确认于
2025/12/02 03:49
3 个月前
查看原文
先倒序枚举 aa 和 bb。
由于 a,b,c,d,na,b,c,d,n 都是正整数，所以 a×b>0a\times b>0，c×d>0c\times d>0，a×b>c×da\times b>c\times d 那么就有：
剪枝①：如果当前 a×b≤na\times b \le n，直接退出。
再枚举 cc。
剪枝②：
题目条件 a×b−c×d=na\times b-c\times d=n 可转化为 a×b−nd=c\frac{a\times b-n}{d}=c，由于 d<bd<b，所以 dd 的最大值为 b−1b-1，所以 cc 的最小值为 max⁡(1,a×b−nb−1)\max(1,\frac{a\times b-n}{b-1})。又因为 c<ac<a，所以 cc 的枚举范围是从 max⁡(1,a×b−nb−1)\max(1,\frac{a\times b-n}{b-1}) 到 a−1a-1。
最后 d=a×b−ncd=\frac{a\times b-n}{c}，再判断 a,b,c,da,b,c,d 是否满足条件即可。
参考代码CPP
//Author: mairuisheng
//#pragma GCC optimize(3)
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char s;
	s=getchar();
	while(s<48||s>57)
	{
		if(s=='-')f=-f;
		s=getchar();
	}
	while(s>47&&s<58)
	{
		x=(x<<3)+(x<<1)+s-48;
		s=getchar();
	}
	return x*f;
}
int n,x;
int ans;
int main()
{
	n=read();
	x=read();
	int i,j,k,l;
	for(i=n;i>0;--i)
	{
		if(i==x)continue;
		for(j=n;j>=i;--j)
		{
			if(j==x)continue;
			if(i*j<=n)break;
			l=i*j-n;
			for(k=max(1,l/(j-1));k<i;++k)
			{
				if(l%k!=0||l/k>=j)continue;
				++ans;
				if(i!=j)++ans;
			}
		}
	}
	printf("%d",ans);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...