阿里笔试 9.8 上午

#include <climits>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

uint64_t solve(uint64_t n, int k)
{
    if (k <= 1)
        return 0;
    vector<int> arr;
    do {
        arr.push_back(n%k);
        n /= k;
    } while (n);

    uint64_t ret = 0;
    for (int e : arr)
        ret = ret*k + e;

    return ret;
}

int main()
{
    int t, k;
    uint64_t n;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

#include <cmath>
#include <cstdio>
#include <climits>

#include <iostream>

using namespace std;

static int64_t func(int64_t sum, int64_t sline, int n, int d, int k)
{
    return sum - 2 * k * sline - n * k * (k-1) * d;
}

pair<int, int64_t> solve(int64_t sum, int64_t sline, int n, int d, int maxk)
{
    int64_t mins = INT64_MAX;
    int k;
    int lo = 1, hi = maxk;
    while (lo <= hi) {
        int mid = lo + (hi-lo)/2;
        auto s = func(sum, sline, n, d, mid);
        printf("k: %d, delta: %d\n", mid, (int)s);
        if (abs(s) < mins || (abs(s) == mins && mid < k)) {
            mins = abs(s);
            k = mid;
        }
        if (s > 0) {
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }
    return {k, mins};
}

void print_solve(int64_t n, uint64_t m)
{
    int64_t sum = n*m*(n*m+1)/2;
    int64_t col_sum = n + n*(n-1)*m/2;
    int64_t row_sum = m*(m+1)/2;
    auto col_min = solve(sum, col_sum, n, 1, m-1);
    auto row_min = solve(sum, row_sum, m, m, n-1);
    cout << "sum: " << sum << endl;
    cout << "col_sum: " << col_sum << endl;
    cout << "row_sum: " << row_sum << endl;
    printf("col_min: {%d, %zd}\n", col_min.first, col_min.second);
    printf("row_min: {%d, %zd}\n", row_min.first, row_min.second);
    if (col_min.second <= row_min.second) {
        cout << "V " << col_min.first << endl;
    } else {
        cout << "H " << row_min.first << endl;
    }
}

int main()
{
    int t;
    int64_t n, m;
    cin >> t;
    while (t--) {
        cin >> n >> m;
        print_solve(n, m);
    }
    return 0;
}