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

lkjzyd20 · 2024-08-21 16:31:56 · 题解

思路 1

观察式子，不妨设 a=c+t,b=d+w，那么有 (c+t)(d+w)-cd=n，即 cw+td+tw=n，考虑枚举 t,w，注意到 c,d,t,w>0，所以 tw<n，所以 w\leq\lfloor\frac nt\rfloor，那么问题转化成 cw+td=n-tw 的正整数解，其中 t,w,n 已知，故可使用 exgcd，时间复杂度为 O(n \log^2 n)。

但还要注意 a\neq x，b\neq x，所以答案要减去 a=x 或 b=x 的情况。

考虑容斥，答案即为 a=x 时的答案加上 b=x 时的答案减去 a=x 且 b=x 的答案，后者整除分块容易解决，考虑前者（这里只考虑 a=x 的情况，b=x 同理），注意到 b\le n，考虑枚举 c，那么转化成求 xb-cd=n 的正整数解，其中 x,c,n 已知，可以使用 exgcd，时间复杂度为 O(n\log n)。

综上所述，时间复杂度为 O(n\log^2n)。

思路 2

当然是暴力加优化了。

我们固定 a,b 和 c。然后我们可以发现 d 是由方程 ab-cd=n 的唯一确定的：如果 ab-n 是 c 的倍数，那么 d=(ab-n)\div c，否则没有合适的 d。注意记得要检查 b>d。

综上所述，时间复杂度 O(n^3)。

思路 2 代码如下

#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
int n, x, ans;
main()
{
    cin >> n >> x;
    for(int i = 1; i <= n + 1;++ i)
    {
        if(i == x) continue;
        rep(j, i, n + 1)
        {
            if(j == x || i * j <= n) continue;
            rep(k, max(1, (i * j - n) / j), i - 1)
            {
                if((i * j - n) / k >= j) continue;
                if((i * j - n) % k == 0) ans += 1 + (i != j);
            }
        }
    }
    printf("%d", ans);
    return 0;
}