問題A：平方倍数の探索

問題概要

正の整数 k が与えられる。k | n^2 （n^2 は k の倍数）かつ n が k の倍数ではないという条件を満たす最小の正の整数 n を求める。

解法の考察

求める n^2 は k の倍数であるため、n^2 = m * k と表せる。ここで n は k の倍数ではないため、m は 1 以上 k-1 以下の範囲に存在する。m を直接全探索すると計算量が O(k) となりTLEする。

そこで、m * k が完全平方数となるかを m が k の約数である場合とそうでない場合に分けて効率的に判定する。m を 1 から √k まで走査し、m * k が完全平方数になるか確認する。同時に、k / m が整数となる場合（すなわち m が k の約数である場合）、(k / m) * k が完全平方数になるかも確認する。これにより、O(√k) の時間計算量で解を求めることができる。

注意点： k が大きい場合、m * k や (k / m) * k は64ビット整数の範囲を超えるため、__int128 を用いてオーバーフローを防ぐ必要がある。

実装例

#include <iostream>
#include <cmath>

using namespace std;
using int128 = __int128_t;

int128 read_int128() {
    int128 val = 0;
    int sign = 1;
    char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') sign = -1; c = getchar(); }
    while (c >= '0' && c <= '9') { val = val * 10 + (c - '0'); c = getchar(); }
    return val * sign;
}

void write_int128(int128 val) {
    if (val < 0) { putchar('-'); val = -val; }
    if (val > 9) write_int128(val / 10);
    putchar(val % 10 + '0');
}

int main() {
    int128 target = read_int128();
    int128 ans = -1;
    for (int128 i = 1; i * i <= target; i++) {
        int128 mul1 = i * target;
        int128 root1 = sqrt((double)mul1);
        if (root1 * root1 == mul1) {
            if (ans == -1 || root1 < ans) ans = root1;
        }
        if (target % i == 0 && i != 1) {
            int128 mul2 = (target / i) * target;
            int128 root2 = sqrt((double)mul2);
            if (root2 * root2 == mul2) {
                if (ans == -1 || root2 < ans) ans = root2;
            }
        }
    }
    write_int128(ans);
    return 0;
}

問題B：隣接交換と組み合わせ

問題概要

n 個の要素からなる数列 a が与えられる。gcd(a_i, a_{i+1}) = 1 である場合、a_i と a_{i+1} を交換できる。交換操作を任意回行った後に得られる異なる数列の数（元の数列を含む）を求める。

解法の考察

互いに素な隣接要素は自由に入れ替え可能である。これは、バブルソートのように任意の相対順序を構築できることを意味する。したがって、互いに素な要素群は1つのブロックとして扱うことができ、ブロック内の要素は任意の順序に並べ替えることが可能である。

異なる数列の総数は、各ブロックのサイズに基づく多重組み合わせ（マルチノミアル係数）として計算される。全体の順列の数を n! とし、各要素の出現回数や各ブロック内の要素の組み合わせに基づいて重複を除くため、各要素の階乗の逆元を掛けることで解を求める。

実装例

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;
const int MAXN = 100005;

long long fact[MAXN], inv_fact[MAXN];
int freq[15];

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> blocks;
    blocks.push_back({0, 0});
    
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        freq[val]++;
        if (val == 6) {
            blocks.push_back({0, 0});
        } else if (val % 2 == 0) {
            blocks.back().first++;
        } else if (val % 3 == 0) {
            blocks.back().second++;
        }
    }
    
    fact[0] = 1;
    for (int i = 1; i <= n; i++) fact[i] = (fact[i - 1] * i) % MOD;
    inv_fact[n] = power(fact[n], MOD - 2);
    for (int i = n - 1; i >= 0; i--) inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    
    int fixed_cnt = freq[1] + freq[5] + freq[7];
    long long res = (fact[n] * inv_fact[n - fixed_cnt]) % MOD;
    
    for (auto& blk : blocks) {
        res = (res * fact[blk.first + blk.second]) % MOD;
        res = (res * inv_fact[blk.first]) % MOD;
        res = (res * inv_fact[blk.second]) % MOD;
    }
    
    res = (res * inv_fact[freq[1]]) % MOD;
    res = (res * inv_fact[freq[5]]) % MOD;
    res = (res * inv_fact[freq[7]]) % MOD;
    
    cout << res << endl;
    return 0;
}

問題C：対頂ヒープによる操作コスト最小化

問題概要

長さ n の数列 x に対し、以下の操作が行える。

1. コスト a を支払い、任意の要素の値を 1 増やす。
2. コスト b を支払い、任意の要素の値を 1 減らす。

各 i (1 <= i <= n) について、x_1 = x_2 = ... = x_i とするための最小コストを求める。

解法の考察

プレフィックスの要素を全て同じ値 T にするコストは、T 未満の要素に対する増分コストと T 超過の要素に対する減分コストの和となる。このコスト関数は T に対して下に凸の関数となるため、最適な T はコストの傾きが変わる重み付き中央値付近に存在する。

重み付き中央値を動的に維持するために、対頂ヒープ（最大ヒープと最小ヒープのペア）を用いる。要素を追加する際、現在の中央値との大小関係に基づいて適切なヒープに挿入する。増分コスト a と減分コスト b の比率を考慮してヒープのサイズバランスを調整し、常に最適な目標値 T を最大ヒープの先頭から取得できるようにする。これにより、全体で O(n log n) の時間計算量で各 i に対する最小コストを求めることができる。

実装例

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    long long cost_inc, cost_dec;
    cin >> n >> cost_inc >> cost_dec;
    
    priority_queue<long long> max_heap;
    priority_queue<long long, vector<long long>, greater<long long>> min_heap;
    
    long long left_sum = 0, right_sum = 0;
    long long median = 0;
    
    for (int i = 1; i <= n; i++) {
        long long val;
        cin >> val;
        
        if (max_heap.empty() || val <= max_heap.top()) {
            max_heap.push(val);
            left_sum += val;
        } else {
            min_heap.push(val);
            right_sum += val;
        }
        
        long long left_sz, right_sz;
        if (val <= median) {
            left_sz = (cost_dec * i) / (cost_inc + cost_dec) + 1;
            right_sz = i - left_sz;
        } else {
            right_sz = (cost_inc * i) / (cost_inc + cost_dec);
            left_sz = i - right_sz;
        }
        
        while (max_heap.size() < left_sz) {
            long long top = min_heap.top();
            min_heap.pop();
            max_heap.push(top);
            right_sum -= top;
            left_sum += top;
        }
        while (max_heap.size() > left_sz) {
            long long top = max_heap.top();
            max_heap.pop();
            min_heap.push(top);
            left_sum -= top;
            right_sum += top;
        }
        
        median = max_heap.top();
        long long cost = (median * max_heap.size() - left_sum) * cost_inc 
                       + (right_sum - median * min_heap.size()) * cost_dec;
        cout << cost << "\n";
    }
    return 0;
}

問題D：木上のパス重みクエリ

問題概要

木が与えられる。長さ d の単純パスの重みを 2^d と定義する。q 個のクエリが与えられ、各クエリでは頂点 x と y を通る全ての単純パスの重みの和を求める。

解法の考察

本問題は解答を見送った。