A. Function Height

수평선 위에 $2n+1$개의 점이 있으며, 초기 위치는 $(i, 0)$입니다. 홀수 번째 인덱스의 점만 $y$ 좌표를 1만큼 증가시킬 수 있습니다. 이 과정을 통해 선분 $P_iP_{i+1}$와 $x$축 사이의 면적이 정확히 $k$가 되도록 하고, 모든 점의 최대 높이를 최소화해야 합니다. 가능한 최소값을 구하세요.

전체적으로 $n$개의 점만 조작 가능하며, 각각의 조작은 면적을 1씩 증가시키므로 최대 $k$번의 조작이 가능합니다. 면적 증가를 균일하게 분산시키면 최적해가 됩니다. 따라서 최소 높이는 $\lceil \frac{k}{n} \rceil$이며, 정수 연산으로 표현하면 $(k + n - 1) / n$입니다.

#include <iostream>
using namespace std;
long long n, k;

int main() {
    cin >> n >> k;
    cout << (k + n - 1) / n << '\n';
    return 0;
}

B. Diagonal Walking v.2

원점에서 시작하여 8방향으로 움직일 수 있습니다. 대각선 이동(예: $(\pm1, \pm1)$)과 직선 이동(예: $(\pm1, 0)$ 또는 $(0, \pm1)$)이 가능합니다. 주어진 $k$번의 이동으로 $(x, y)$에 도달할 수 있는지 확인하고, 가능하다면 최대한 많은 대각선 이동 횟수를 출력하세요.

모든 경우는 $|x|, |y|$로 변환할 수 있으므로, $x, y \geq 0$로 가정합니다. 목적지까지 최소 이동 거리는 $\max(x, y)$입니다. 이보다 적은 $k$라면 불가능합니다. 그렇지 않으면 나머지 이동은 반복 이동이나 조정을 통해 대각선 이동을 최대화할 수 있습니다.

• 남은 이동 횟수가 짝수이면, 전체를 대각선으로 활용 가능.
• 홀수면 한 대각선을 두 직선으로 교체하여 짝수로 만듦.
• 남은 직선 이동이 홀수이면, 하나의 직선 이동을 먼저 수행하거나 마지막에 조정.

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

inline ll read() {
    ll t = 0; short f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -f; ch = getchar(); }
    while (ch >= '0' && ch <= '9') t = t * 10 + ch - '0', ch = getchar();
    return t * f;
}

ll n, m, k, mn, mx;

void solve() {
    n = read(); m = read(); k = read();
    n = abs(n); m = abs(m);
    mn = min(n, m); mx = max(n, m);
    if (mx > k) {
        cout << -1 << '\n';
        return;
    }
    k -= mx;
    if ((mx - mn) % 2 == 0) {
        if (k % 2 == 1) cout << k + mx - 2 << '\n';
        else cout << k + mx << '\n';
    } else {
        cout << k + mx - 1 << '\n';
    }
}

int main() {
    int q = read();
    while (q--) solve();
    return 0;
}

C. Classy Numbers

자릿수 중 1~9 사이의 숫자가 3개 이하인 수를 "클래시 수"라고 합니다. 주어진 범위 $[l, r]$ 내의 클래시 수 개수를 세는 문제입니다.

수열 길이가 $10^{18}$까지 가능하므로, 수기법 기반의 동적 프로그래밍(수기법 DP)이 필요합니다. 각 자리에서 비제로 숫자의 개수를 상태로 하여 메모이제이션을 수행합니다. 범위 쿼리에서는 $F(r) - F(l-1)$ 방식으로 처리합니다.

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;

ll dp[20][5];
ll a[20];

ll dfs(int pos, int cnt, bool tight) {
    if (!pos) return 1;
    if (!tight && dp[pos][cnt] != -1) return dp[pos][cnt];
    
    int lim = tight ? a[pos] : 9;
    ll res = 0;
    for (int i = 0; i <= lim; ++i) {
        if (i == 0)
            res += dfs(pos - 1, cnt, tight && (i == lim));
        else if (cnt < 3)
            res += dfs(pos - 1, cnt + 1, tight && (i == lim));
    }
    if (!tight) dp[pos][cnt] = res;
    return res;
}

ll calc(ll x) {
    int len = 0;
    while (x) a[++len] = x % 10, x /= 10;
    return dfs(len, 0, true);
}

int main() {
    memset(dp, -1, sizeof(dp));
    int T;
    cin >> T;
    while (T--) {
        ll l, r;
        cin >> l >> r;
        cout << calc(r) - calc(l - 1) << '\n';
    }
    return 0;
}

D. Vasya and Arrays

두 배열 $a$, $b$를 같은 개수의 연속된 구간으로 나누어, 각 구간의 합이 일치하도록 하는 최대 구간 수 $k$를 찾습니다. 만약 불가능하면 $-1$을 출력합니다.

전체 합이 다를 경우 불가능합니다. 그 외에는 그리디 전략을 사용: 각 배열의 전후 고려 시, 가장 짧은 공통 부분합을 찾아 분할 지점을 설정하면 최적입니다. 배열 $a$의 전부분합을 순회하면서, $b$의 전부분합 중 같은 값이 있는지 `lower_bound`로 검색합니다.

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;

const int MAXN = 3e5 + 7;
int n, m;
ll a[MAXN], b[MAXN];
ll sa[MAXN], sb[MAXN];

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sa[i] = sa[i - 1] + a[i];
    }
    cin >> m;
    for (int i = 1; i <= m; ++i) {
        cin >> b[i];
        sb[i] = sb[i - 1] + b[i];
    }
    
    if (sa[n] != sb[m]) {
        cout << -1 << '\n';
        return 0;
    }
    
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        auto it = lower_bound(sb + 1, sb + m + 1, sa[i]);
        if (it != sb + m + 1 && *it == sa[i]) ++ans;
    }
    cout << ans << '\n';
    return 0;
}

E. Covered Points

$n$개의 선분이 주어지고, 이들이 포함하는 정수 좌표점의 수를 구합니다. 좌표 범위는 $[-10^6, 10^6]$이며, 선분은 점이 아니며 서로 평행하지 않습니다.

각 선분이 지나가는 정수 점 수는 $\gcd(|dx|, |dy|) + 1$로 계산됩니다. 이후, 모든 선분 쌍의 교차점을 구하고, 교차점이 실제 선분 내부에 있는지 확인합니다. 교차점의 좌표는 두 직선 방정식의 해를 구하며, 정수 여부는 나눗셈의 정확성으로 판단합니다.

시간 복잡도는 $O(n^2)$이며, 정밀도 문제에 주의해야 합니다.

F. Relatively Prime Powers

수 $x$의 소인수 분해에서 각 지수의 최대공약수가 1이면 "유효한 제곱수"라 합니다. 예: $12 = 2^2 \cdot 3^1$, $\gcd(2,1)=1$ → 유효. $8 = 2^3$, $\gcd(3)=3$ → 무효.

주어진 범위 $[2, n]$ 내의 유효한 제곱수의 개수를 세는 문제입니다. 지수는 최대 60까지 가능 ($2^{60} > 10^{18}$).

모든 수는 $a^b$ 형태로 표현되며, $b$의 $\gcd$가 1이어야 함. 이를 위해 모비우스 함수 $\mu(b)$를 사용한 포함배제 원리를 적용합니다. 각 $b$에 대해 가능한 $a$의 개수를 계산하고, $\mu(b)$를 곱해 누적합니다.

근의 추정은 `pow` 함수로 하되, 오차를 보정하기 위해 상한을 약간 크게 잡고, 빠른 제곱 연산으로 정확한 값을 찾습니다.

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double db;

db ksm(db x, ll y) {
    db ret = 1;
    while (y) {
        if (y & 1) ret *= x;
        y >>= 1;
        x *= x;
    }
    return ret;
}

int mu[70], prime[70], pcnt;
bool vis[70];

void get_mu(int limit) {
    mu[1] = 1;
    for (int i = 2; i <= limit; ++i) {
        if (!vis[i]) prime[++pcnt] = i, mu[i] = -1;
        for (int j = 1; j <= pcnt && i * prime[j] <= limit; ++j) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
    }
}

ll n;

void solve() {
    cin >> n;
    ll ans = 0;
    for (int i = 1; i <= 60; ++i) {
        if ((1LL << i) > n) break;
        if (i >= 38) {
            ans += mu[i];
            continue;
        }
        ll up = (ll)(pow(n, 1.0L / i) + 2);
        while (ksm(up, i) > n) --up;
        ans += mu[i] * (up - 1);
    }
    cout << ans << '\n';
}

int main() {
    get_mu(65);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}