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

· · 题解

先倒序枚举 a 和 b。

由于 a,b,c,d,n 都是正整数，所以 a\times b>0，c\times d>0，a\times b>c\times d 那么就有：

剪枝①：如果当前 a\times b \le n，直接退出。

再枚举 c。

剪枝②：

题目条件 a\times b-c\times d=n 可转化为 \frac{a\times b-n}{d}=c，由于 d<b，所以 d 的最大值为 b-1，所以 c 的最小值为 \max(1,\frac{a\times b-n}{b-1})。又因为 c<a，所以 c 的枚举范围是从 \max(1,\frac{a\times b-n}{b-1}) 到 a-1。

最后 d=\frac{a\times b-n}{c}，再判断 a,b,c,d 是否满足条件即可。

:::info[参考代码]

//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;
}

:::