CF题解——Garage

算法竞赛相关
编程算法竞赛题解数论二分查找
本文最后更新于 8 个月前，文中所描述的信息可能已发生改变。

G. Garage 解题思路 ​

核心问题分析与数学转化 ​

根据题意，合适的数 xx 必须能被表示为 b2−a2b^2 - a^2，其中 aa 和 bb 是正整数 (a,b∈Z+a, b \in \mathbb{Z}^+) 且 a<ba < b.

我们对平方差公式进行因式分解：

x=b2−a2=(b−a)(b+a)x = b^2 - a^2 = (b - a)(b + a)

设 k=b−ak = b - a，m=b+am = b + a. 为了使 aa 和 bb 为正整数，且 a>0a>0，必须满足以下条件：

  1. x=k⋅mx = k \cdot m
  2. k<mk < m
  3. kk 和 mm 必须具有相同的奇偶性 (因为 b=(m+k)/2b = (m+k)/2 且 a=(m−k)/2a = (m-k)/2 必须是整数)。

2. 排除不合适的数 (Unsuitable Numbers) ​

只有当 xx 不能分解为两个奇偶性相同的因子时，它才是不合适的数。

排除规则 1：基于模 4 性质 (x≡2(mod4)x \equiv 2 \pmod 4) ​

如果一个数 xx 除以 $ 4$ 余 $ 2$（即 x≡2(mod4)x \equiv 2 \pmod 4，如 $ 2, 6, 10, \dots$），它一定不能被表示为 b2−a2b^2 - a^2。 原因：平方数 n2≡0n^2 \equiv 0 或 $ 1 \pmod 4。因此，。因此，b^2 - a^2$ 永远不可能是 $ 2 \pmod 4$. 结论： 所有 x≡2(mod4)x \equiv 2 \pmod 4 的数都不是合适的数。

排除规则 2：特殊情况 x=1x=1 和 x=4x=4

quot;">​
  1. x=1x=1： 因子只有 (1,1)(1, 1). 解得 a=(1−1)/2=0a = (1-1)/2 = 0. 由于 a≥1a \ge 1 必须是正整数，故 x=1x=1 不合适。
  2. x=4x=4： 因子对 (2,2)(2, 2) 奇偶性相同。解得 a=(2−2)/2=0a = (2-2)/2 = 0. 由于 a≥1a \ge 1，故 x=4x=4 不合适。

不合适的数列表 UU： {1,2,4,6,10,14,18,… }\{1, 2, 4, 6, 10, 14, 18, \dots \}.

3. 算法思路：二分查找 ​

我们使用二分查找来寻找第 NN 小的合适数 XNX_N. 我们寻找最小的 XX 使得 CountSuitable(X)≥NCountSuitable(X) \ge N.

CountSuitable(X)=X−CountUnsuitable(X)CountSuitable(X) = X - CountUnsuitable(X)

CountUnsuitable(D)CountUnsuitable(D) 的计算逻辑：

  • if (d >= 1) count += 1; 排除 d=1d=1.

  • if (d >= 4) count += 1; 排除 d=4d=4.

  • if (d >= 2) 部分计算 d≡2(mod4)d \equiv 2 \pmod 4 的数的个数：

    textCountofd≡2(mod4)=⌊D−24⌋+1text{Count of } d \equiv 2 \pmod 4 = \lfloor \frac{D-2}{4} \rfloor + 1

CPP 代码实现 ​

代码通过二分查找，利用 count_suitablecount\_suitable 函数定位第 NN 个合适数。

cpp
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// 计算在 [1, d] 范围内不合适的数的个数
ll count_unsuitable(ll d) {
    ll count = 0;

    // 排除 d=1
    if (d >= 1) {
       count += 1;
    }

    // 排除 d=4
    if (d >= 4) {
       count += 1;
    }

    // 排除 d = 2, 6, 10, ... (d ≡ 2 mod 4 的数)
    if (d >= 2) {
       // 计算 [2, d] 中 4k + 2 形式的数的个数
       ll count_mod_2 = (d - 2) / 4 + 1;
       count += count_mod_2;
    }

    return count;
}

// 计算在 [1, d] 范围内合适数的个数
ll count_suitable(ll d) {
    if (d < 3) return 0;

    ll unsuitable_count = count_unsuitable(d);
    return d - unsuitable_count;
}

void solve() {

    ll N;
    cin >> N;

    ll low = 1;
    // 上限可以保守估计为 4N，因为不合适数比例约为 1/4
    ll high = N * 4 + 5; 
    
    ll ans = high;

    while (low <= high) {
       ll mid = low + (high - low) / 2;
        
       if (mid < 1) {
          low = 1;
          continue;
       }

       ll suitable_count = count_suitable(mid);

       if (suitable_count >= N) {
          // mid 是一个可能的答案，尝试更小的值
          ans = mid;
          high = mid - 1;
       } else {
          // mid 太小，合适的数数量不足 N
          low = mid + 1;
       }
    }

    cout << ans << '\n';
}

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;

    while (t--) {
       solve();
    }

}
CF题解——Fibonacci Paths
CF题解——Beppa and SwerChat