算法基础学习笔记——⑭欧拉函数\快速幂\扩展欧几里得算法\中国剩余定理

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int eulerTotient(int n) {
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (gcd(n, i) == 1) {
            count++;
        }
    }
    return count;
}

int main() {
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    int result = eulerTotient(n);
    printf("Euler's Totient Function of %d is %d\n", n, result);
    return 0;
}

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

int primes[N], cnt; // primes[]存储所有素数,cnt存储每个素数的下标
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
     euler[1] = 1;
     for (int i = 2; i <= n; i ++ )
     {
         if (!st[i])
         {
             primes[cnt ++ ] = i;
             euler[i] = i - 1;
         }
         for (int j = 0; primes[j] <= n / i; j ++ )
         {
             int t = primes[j] * i;
             st[t] = true;
             if (i % primes[j] == 0)
             {
                 euler[t] = euler[i] * primes[j];
                 break;
             }
             euler[t] = euler[i] * (primes[j] - 1);
         }
     }
}

#include <stdio.h>
long long fastExponentiation(int base, int exponent) {
    long long result = 1;
    while (exponent > 0) {
        if (exponent % 2 == 1) {
            result *= base;
        }
        base *= base;
        exponent /= 2;
    }
    return result;
}
int main() {
    int base, exponent;
    printf("Enter the base: ");
    scanf("%d", &base);
    printf("Enter the exponent: ");
    scanf("%d", &exponent);
    long long result = fastExponentiation(base, exponent);
    printf("%d raised to the power of %d is %lld\n", base, exponent, result);
    return 0;
}

#include <stdio.h>
int extendedEuclidean(int a, int b, int *x, int *y) {
    // 初始情况
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = extendedEuclidean(b % a, a, &x1, &y1);

    // 更新x和y
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}
int main() {
    int a, b;
    printf("Enter two numbers: ");
    scanf("%d %d", &a, &b);
    int x, y;
    int gcd = extendedEuclidean(a, b, &x, &y);
    printf("GCD: %d\n", gcd);
    printf("Coefficients (x, y): (%d, %d)\n", x, y);
    return 0;
}

#include <stdio.h>
int extendedEuclidean(int a, int b, int *x, int *y) {
    // 初始情况
    if (a == 0) {
        *x = 0;
        *y = 1;
        return b;
    }
    int x1, y1;
    int gcd = extendedEuclidean(b % a, a, &x1, &y1);
    // 更新x和y
    *x = y1 - (b / a) * x1;
    *y = x1;
    return gcd;
}
int modInverse(int a, int m) {
    int x, y;
    int gcd = extendedEuclidean(a, m, &x, &y);
    if (gcd != 1) {
        printf("Inverse doesn't exist\n");
        return -1;
    }
    int result = (x % m + m) % m;
    return result;
}
int chineseRemainder(int num[], int rem[], int n) {
    int prod = 1;
    for (int i = 0; i < n; i++) {
        prod *= num[i];
    }
    int result = 0;
    for (int i = 0; i < n; i++) {
        int pp = prod / num[i];
        int inv = modInverse(pp, num[i]);
        result += rem[i] * pp * inv;
    }
    result %= prod;
    return result;
}
int main() {
    int num[10], rem[10], n;
    printf("Enter the number of equations: ");
    scanf("%d", &n);
    printf("Enter the values of equations (num and rem):\n");
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &num[i], &rem[i]);
    }
    int result = chineseRemainder(num, rem, n);
    printf("Solution: %d\n", result);
    return 0;
}