模余运算1计算2^1000000mod 772计算312^13mod667要求：一利用C语言编程实现模余运算快速算法;

1）利用快速幂算法，将指数1000000转化为二进制形式，然后每次将底数平方取模，如果该位为1，则再乘上原来的底数再取模。

C语言代码实现：

int mod_pow(int base, int exp, int mod) { int res = 1; while (exp > 0) { if (exp & 1) { res = (res * base) % mod; } base = (base * base) % mod; exp >>= 1; } return res; }

int main() { int ans = mod_pow(2, 1000000, 77); printf("%d", ans); return 0; }

2）利用扩展欧几里得算法和快速幂算法，将指数13拆分成2+2+2+2+2+2+1的形式，然后每次将底数平方取模，根据指数的每个2次幂的系数进行乘法运算，最后再对结果取模。

C语言代码实现：

int mod_pow(int base, int exp, int mod) { int res = 1; while (exp > 0) { if (exp & 1) { res = (res * base) % mod; } base = (base * base) % mod; exp >>= 1; } return res; }

int mod_inverse(int a, int mod) { int x1 = 1, x2 = 0, x3 = mod; int y1 = 0, y2 = 1, y3 = a; int q, t1, t2, t3; while (y3 != 1 && y3 != 0) { q = x3 / y3; t1 = x1 - q * y1; t2 = x2 - q * y2; t3 = x3 - q * y3; x1 = y1; x2 = y2; x3 = y3; y1 = t1; y2 = t2; y3 = t3; } if (y3 == 0) { printf("Error: %d has no inverse modulo %d", a, mod); return 0; } if (y2 < 0) { y2 += mod; } return y2; }

int mod_mul(int a, int b, int mod) { int res = 0; while (b > 0) { if (b & 1) { res = (res + a) % mod; } a = (a << 1) % mod; b >>= 1; } return res; }

int mod_pow_multi(int base, int exp[], int exp_len, int mod) { int res = 1; for (int i = 0; i < exp_len; i++) { int tmp = mod_pow(base, exp[i], mod); int inv = mod_inverse(tmp, mod); res = mod_mul(res, inv, mod); base = mod_pow(base, 2, mod); } return res; }

int main() { int exp[] = {2, 2, 2, 2, 2, 2, 1}; int ans = mod_pow_multi(312, exp, 7, 667); printf("%d", ans); return 0;