题解：CF2045B ICPC Square

· · 题解

设答案为 ans=s \times p_1 \times p_2 \times \ldots \times p_k，那么发现将 p 降序排序一定是不劣的，于是设 t=\prod_{i=1}^{k-1} p_i。考虑答案会满足什么限制：

ans=s \times v \times p_k

然后 v 满足下面两个条件：

  • s \times p_k \times v \le n
  • s \times p_k \times (v - 1) \le d

综合一下就有：v \le \min(\lfloor \frac{n}{s \times p_k} \rfloor,\lfloor \frac{d}{s \times p_k} \rfloor + 1)

这接对这个式子整除分块就行了，这里再介绍个结论： \lfloor \frac{n}{a \times b} \rfloor = \lfloor\frac{\lfloor \frac{n}{a} \rfloor}{b} \rfloor。这样就可以正常整出分块了。

::::success[代码]

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, d, s;

int main() {
    cin >> n >> d >> s;
    n /= s, d /= s;
    ll p1 = 1, p2 = 1, ans = s;
    while(p1 <= n && p2 <= d) {
        ll r1 = n / (n / p1), r2 = d / (d / p2);
        ll v = min(n / p1, d / p2 + 1);
        ans = max(ans, s * min(r1, r2) * v);
        if(r1 < r2) p1 = r1 + 1;
        else p2 = r2 + 1;
    }
    cout << ans << "\n";
    return 0;
}

::::