设计求算法解a n mod m其中a n和m均为大于1的整数 C语言实现

在C语言中，设计求解a^n模m的问题通常需要利用快速幂算法（Fast Exponentiation Algorithm），也称为欧几里得算法的扩展版本。这个算法可以在O(log n)的时间复杂度内完成计算，避免了直接对大整数做n次乘法导致的效率低下。

以下是C语言中基于快速幂算法的一个简单实现：

#include <stdio.h>

// 计算 a^b (mod m)
long long fastModPow(long long a, long long b, long long m) {
    long long res = 1; // 初始化结果为1
    while (b > 0) {
        // 如果b为偶数，将a自乘并将b除以2
        if (b % 2 == 0) {
            a = (a * a) % m;
            b /= 2;
        } else { // 如果b为奇数，将当前的结果乘以a并更新b
            res = (res * a) % m;
            b--;
        }
    }
    return res;
}

int main() {
    int a, n, m;
    printf("请输入a, n和m的值: ");
    scanf("%d %d %d", &a, &n, &m);
    
    if (m <= 0 || a == 0 || n <= 0) {
        printf("输入错误! 确保a, n和m都是大于0的整数。\n");
    } else {
        long long result = fastModPow(a, n, m);
        printf("a^%d mod %d = %lld\n", n, m, result);
    }

    return 0;
}

当你运行这个程序时，它会提示用户输入a、n和m的值，然后计算a的n次方对m取余的结果。请注意，输入的数值必须是非负整数，因为模运算在此场景下通常只适用于正整数。