标签： 数论

扩展欧几里得

int gcd(int const a, int const b) {
    return !b ? a : gcd(b, a
}

int lcm(int const a, int const b) {
    return a / gcd(a, b) * b;
}

int exgcd(int const a, int const b, int &x, int &y) {
    int ans = a;
    if (b == 0) {
        x = 1, y = 0;
        return ans;
    }
    else {
        ans = exgcd(b, a
        y -= x * (a / b);
        return ans;
    }
}

欧拉筛

bool is_prime[MAXN];
int primes[MAXN], query[MAXM];
int n, m, p;

void sieve(int const n) {
    memset(primes, 0, sizeof(primes));
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[1] = false;
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes[p++] = i;
        }
        for (int j = 0; j < p && i * primes[j] <= n; j++) {
            is_prime[ i * primes[j] ] = false;
            if (! (i
                break;
        }
    }
}