Counting GCD Pairs in Dynamic Multisets

Maintain a multiset of positive integers with insertion and deletion operations. For each query, count unordered pairs (i, j) where i ≠ j and gcd(i, j) = k.

Constraints: n, V ≤ 10^5.

Conisder the change in answer count:

$$\sum_{i=1}^{V}c_i[\gcd(i,x)=k]$$

Let x' = x/k:

$$\sum_{i=1}^{\lfloor V/k \rfloor}c_{ik}[\gcd(i,x')=1]$$

$$\sum_{p|x'}\mu(p)\sum_{i=1}^{\lfloor V/(pk) \rfloor}c_{ipk}$$

Maintain with O(n·max{σ(a)}) complexity.

#include <bits/stdc++.h>
using namespace std;
const int MAX = 100010;

int query_count, target_gcd;
vector<int> divisors[MAX];
int primes[MAX/2], prime_count;
bool composite[MAX];
int moebius[MAX];
int frequency[MAX], divisor_sum[MAX];
long long total_pairs;

void initialize() {
    for (int i = 1; i < MAX; i++)
        for (int j = i; j < MAX; j += i)
            divisors[j].push_back(i);
    
    moebius[1] = 1;
    for (int i = 2; i < MAX; i++) {
        if (!composite[i]) {
            primes[++prime_count] = i;
            moebius[i] = -1;
        }
        for (int j = 1; j <= prime_count && i * primes[j] < MAX; j++) {
            composite[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
            moebius[i * primes[j]] = -moebius[i];
        }
    }
}

int compute(int val) {
    int result = 0;
    for (int d : divisors[val])
        result += moebius[d] * divisor_sum[target_gcd * d];
    return result;
}

int main() {
    cin >> query_count >> target_gcd;
    initialize();
    
    for (int i = 0; i < query_count; i++) {
        int operation, value;
        cin >> operation >> value;
        
        if (value % target_gcd) {
            cout << total_pairs << endl;
            continue;
        }
        
        if (operation == 0) {
            if (!frequency[value]) {
                cout << total_pairs << endl;
                continue;
            }
            frequency[value]--;
            for (int d : divisors[value]) divisor_sum[d]--;
            total_pairs -= compute(value / target_gcd);
        } else {
            total_pairs += compute(value / target_gcd);
            frequency[value]++;
            for (int d : divisors[value]) divisor_sum[d]++;
        }
        cout << total_pairs << endl;
    }
    return 0;
}

Minimum Operations for Array Construction

Given array {h_n}, start with empty array {a_n}. Operations allowed:

• Choose i ∈ [1, n-1]: a_i += 1, a_{i+1} += 2
• Choose i ∈ [1, n-1]: a_i += 2, a_{i+1} += 1

Find minimum operations to achieve ∀i ∈ [1, n], a_i ≥ h_i.

Constraints: n, h ≤ 10^6.

Use greedy with backtracking:

• For executed a_i+2, a_{i+1}+1 operations, consider converting to two a_i+1, a_{i+1}+2 operations
• For executed a_i+3 operations, convert to combinations of basic operations
• Prioritize minimizing operations on left elements

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000010;

int n, target[MAXN];
int carry[MAXN];
long long operation_count;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> target[i];
    
    int op1 = 0, op2 = 0, op3 = 0;
    for (int i = 1; i <= n; i++) {
        target[i] = max(0, target[i]);
        
        int use3 = min(target[i] / 3, carry[i]);
        target[i] -= use3 * 3;
        
        int use2 = target[i] / 2;
        target[i] -= use2 * 2;
        
        int use1 = target[i];
        target[i] -= use1;
        
        operation_count += use3 + use2 + use1;
        carry[i+1] += use3 * 2 + use2;
        target[i+1] -= use2 + use1 * 2;
    }
    
    cout << operation_count << endl;
    return 0;
}

Circular Coloring with Adjacency Constraints

Color n beads in a circle with k colors or leave uncolored. Adjacent beads cannot both be colored. Count rotationally distinct solutions modulo 10^9+7.

Constraints: n, k ≤ 10^9.

Apply Burnsdie's lemma: L = (1/|G|) Σ c1(g)

For rotation by i positions, let t = gcd(n, i). Group beads into t cycles of n/t beads. Coloring constraint: beads in same cycle must have same color, adjacent cycles cannot both be colored.

Define state matrix for dynamic programming:

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

struct Matrix {
    int data[4][4];
    Matrix() { memset(data, 0, sizeof(data)); }
    
    Matrix operator*(const Matrix& other) const {
        Matrix result;
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                for (int k = 0; k < 4; k++)
                    result.data[i][j] = (result.data[i][j] + 1LL * data[i][k] * other.data[k][j]) % MOD;
        return result;
    }
};

Matrix matrix_power(Matrix base, int exponent) {
    Matrix result;
    for (int i = 0; i < 4; i++) result.data[i][i] = 1;
    
    while (exponent) {
        if (exponent & 1) result = result * base;
        base = base * base;
        exponent >>= 1;
    }
    return result;
}

int compute_cycle(int cycle_length, int colors) {
    Matrix transition;
    transition.data[0][0] = transition.data[1][0] = 1;
    transition.data[0][1] = colors;
    transition.data[2][2] = transition.data[3][2] = 1;
    transition.data[2][3] = colors;
    
    Matrix initial;
    initial.data[0][0] = 1;
    initial.data[0][3] = colors;
    
    Matrix result = initial * matrix_power(transition, cycle_length - 1);
    return (1LL * result.data[0][0] + result.data[0][1] + result.data[0][2]) % MOD;
}

int euler_phi(int x) {
    int result = x;
    for (int i = 2; i * i <= x; i++) {
        if (x % i) continue;
        result -= result / i;
        while (x % i == 0) x /= i;
    }
    if (x > 1) result -= result / x;
    return result;
}

int mod_inverse(int x) {
    return pow(x, MOD - 2, MOD);
}

int main() {
    int n, k;
    cin >> n >> k;
    
    long long total = 0;
    for (int i = 1; i * i <= n; i++) {
        if (n % i) continue;
        total = (total + 1LL * compute_cycle(i, k) * euler_phi(n / i)) % MOD;
        if (i * i != n) total = (total + 1LL * compute_cycle(n / i, k) * euler_phi(i)) % MOD;
    }
    
    total = 1LL * total * mod_inverse(n) % MOD;
    cout << total << endl;
    return 0;
}