最大公约数、最小公倍数、素数判断、快速幂、扩展欧几里得算法、欧拉函数

admin

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

// 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计算（lcm(a,b) = a*b/gcd(a,b)）
long long lcm(long long a, long long b) {
    if (a == 0 || b == 0) return 0; // 避免除以零
    return a / gcd(a, b) * b; // 先除后乘，避免溢出
}

// 3. 素数判断（试除法）
bool isPrime(int n) {
    if (n <= 1) return false; // 小于等于1的数不是素数
    if (n == 2) return true;  // 2是素数
    if (n % 2 == 0) return false; // 偶数不是素数
    
    // 检查到sqrt(n)即可，只需检查奇数
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

// 4. 快速幂（模运算优化）：计算 (base^exponent) % mod
long long fastPower(long long base, long long exponent, long long mod) {
    long long result = 1;
    base %= mod; // 防止base过大
    
    while (exponent > 0) {
        // 如果指数为奇数，将当前base乘到结果中
        if (exponent % 2 == 1) {
            result = (result * base) % mod;
        }
        // 指数折半，base平方
        base = (base * base) % mod;
        exponent /= 2;
    }
    return result;
}

// 5. 扩展欧几里得算法：求解 ax + by = gcd(a,b) 的一组解
long long extendedGCD(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long x1, y1;
    long long g = extendedGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}

// 6. 欧拉函数：计算小于n且与n互质的正整数个数
int eulerPhi(int n) {
    if (n == 0) return 0;
    int result = n;
    // 质因数分解
    for (int p = 2; p * p <= n; p++) {
        if (n % p == 0) {
            // 消除所有p的因子
            while (n % p == 0) {
                n /= p;
            }
            result -= result / p;
        }
    }
    // 若剩余n为质数
    if (n > 1) {
        result -= result / n;
    }
    return result;
}

int main() {
    // 测试最大公约数
    long long a = 48, b = 18;
    cout << "1. GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
    
    // 测试最小公倍数
    cout << "2. LCM(" << a << ", " << b << ") = " << lcm(a, b) << endl;
    
    // 测试素数判断
    int num = 97;
    cout << "3. " << num << (isPrime(num) ? " 是素数" : " 不是素数") << endl;
    
    // 测试快速幂
    long long base = 2, exponent = 10, mod = 1000;
    cout << "4. " << base << "^" << exponent << " mod " << mod << " = " << fastPower(base, exponent, mod) << endl;
    
    // 测试扩展欧几里得算法
    long long x, y;
    long long g = extendedGCD(15, 10, x, y);
    cout << "5. 15*" << x << " + 10*" << y << " = " << g << endl;
    
    // 测试欧拉函数
    int n = 12;
    cout << "6. 欧拉函数φ(" << n << ") = " << eulerPhi(n) << endl;
    cout << "   （小于" << n << "且与" << n << "互质的数有：1, 5, 7, 11，共4个）" << endl;
    
    return 0;
}