백준 10793번 Tile Cutting

문제 요약

직사각형 모양의 타일이 있을 때, 해당 직사각형에서 평행사변형 모양의 타일을 떼어낼 것이다. 직사각형 모양의 타일은 전부 변의 길이가 정수이다.

평행사변형을 떼어내는 방법을 막 설명하는데 요점은 평행사변형의 모든 꼭짓점이 직사각형의 각 변위에 놓여야 하며 꼭짓점이 놓일 수 있는 위치는 정수 점들 뿐이다.

이 때, lo, hi가 주어지는데 이는 평행사변형의 넓이를 뜻한다. lo부터 hi까지의 넓이를 갖는 평행사변형을 만들려고 하는데 만드는 방법의 수가 가장 많은 넓이를 찾고 그 방법의 수를 출력하는 것이다.

풀이

일단 어떤 직사각형이 주어지고 그 직사각형에서 유효한 평행사변형 하나를 만들었다고 하자. 그러면 아래와 같은 꼴이 될 것이다.

이 평행 사변형의 넓이는 직사각형의 넓이에서 네 귀퉁이에 있는 삼각형의 넓이를 뺀 $(a+b)(c+d)-ac-bd=ad+bc$가 된다.

여기서 $a, b, c, d$는 자연수이다. 위 식을 토대로 어떤 평행 사변형의 넓이가 $S$라면, $S$를 나타내는 방법은 $1+(S-1), 2+(S-2), \cdots (S-2)+2, (S-1)+1$으로 총 $S-1$가지 경우가 생긴다. 그리고 더해지는 두 수는 어떤 두 자연수의 곱이 된다.

그러면 이제 $s_i=\text{(두 자연수를 곱해서 i가 되는 경우의 수)}$라고 하자. 그러면 $S$를 나타내는 방법은 아래와 같이 표현된다.
$$
\sum_{i=1}^{S-1}s_is_{S-i}
$$
$s_i$를 구하는 것은 에라토스테네스의 체를 이용하면 가능하다. 그리고 $S$는 최대 50만이므로 모든 $S$에 대해서 위의 값을 구하면 문제를 풀 수 있다.

위의 식은 Convolution의 꼴로 $s_i$를 1부터 50만까지 구한 다음에 $s$끼리 Convolution한 결과인 $s*s$를 구하면 된다.

이걸로 문제를 풀 수 있다.

#include<bits/stdc++.h>
#define MAXN 500000
using namespace std;
using ll = long long;
using cdbl = complex<double>;
const double PI = acos(-1);
void fft(vector<cdbl> &a, bool inv) {
    int n = a.size();
    // bit reversal
    for (int i = 1, j = 0; i<n; ++i) {
        int bit = n >> 1;
        while (!((j ^= bit) & bit)) bit >>= 1;
        if (i<j) swap(a[i], a[j]);
    }
    for (int i = 1; i<n; i <<= 1) {
        double x = inv ? PI / i : -PI / i;
        cdbl w = cdbl(cos(x), sin(x));
        for (int j = 0; j<n; j += i << 1) {
            cdbl p = cdbl(1, 0);
            for (int k = 0; k<i; ++k) {
                cdbl tmp = a[i + j + k] * p;
                a[i + j + k] = a[j + k] - tmp;
                a[j + k] += tmp;
                p *= w;
            }
        }
    }
    if (inv) {
        for (int i = 0; i<n; ++i) a[i] /= n;
    }
}

// h = fg
vector<ll> multiply(vector<ll> &f, vector<ll> &g) {
    vector<cdbl> pf(f.begin(), f.end()), pg(g.begin(), g.end());
    int n = 1; while (n < f.size() + g.size()) n <<= 1;
    pf.resize(n); pg.resize(n);
    fft(pf, false); fft(pg, false);
    for (int i = 0; i < n; ++i) pf[i] *= pg[i];
    fft(pf, true);
    vector<ll> ret(n);
    for (int i = 0; i < n; ++i) {
        ret[i] = (ll)round(pf[i].real());
    }
    return ret;
}

int N;
vector<ll> divisor(500005,0);
int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    for (int i = 1; i <= MAXN; ++i) 
        for (int j = i; j <= MAXN; j += i) 
            ++divisor[j];
    vector<ll> ans = multiply(divisor, divisor);
    ans[1] = 1;
    for (int i = 0; i < N; ++i) {
        int lo, hi;
        cin >> lo >> hi;
        int idx = lo;
        for (int i = lo+1; i <= hi; ++i) {
            if (ans[idx] < ans[i]) 
                idx = i;
        }
        cout << idx << ' ' << ans[idx] << '\n';
    }
    return 0;
}