数学

// 1. 最大公约数（GCD）- 欧几里得算法（迭代版）
long long gcd(long long a, long long b) {
    while (b != 0) {
        long long temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 2. 最小公倍数（LCM）- 基于GCD计算
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0; // 0和任何数的最小公倍数是0
    return (a / gcd(a, b)) * b; // 先除后乘避免溢出
}

vector<int> primeFactorization(int n) {
    vector<int> factors;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) factors.push_back(n);
    return factors;
}

bool isnp[MAXN]; // is not prime: 不是素数
void init(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (!isnp[i])
            for (int j = i * i; j <= n; j += i)
                isnp[j] = 1;
}

bool isnp[MAXN];
vector<int> primes; // 质数表
void init(int n)
{
    for (int i = 2; i <= n; i++)
    {
        if (!isnp[i])
            primes.push_back(i);
        for (int p : primes)
        {
            //越界退出 使用乘法快于除法
            if (p * i > n)
                break;
            isnp[p * i] = 1;
            //合数只筛一次 保证是被最小质因数筛除
            if (i % p == 0)
                break;
        }
    }
}

long long quickpow(long long a,long long n)
{
    long long res=1;
    while(n>0)
    {
        if(n&1) res*=a;//如果指数当前二进制位数字为1，则乘上这个
        a=a*a;//待乘指数向前一位
        n>>=1;//指数当前位数向前一位
    }
    return res;
}