c语言快速幂算法

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int call(int a, int b, int p)
{
    int r = 1;
    int u = b;
    int c = 0;
    int d = 0;
    int e = 0;

    if(p == 1)
    {
        return 0;
    }

    while(u > 0)
    {
        if(u & 1)
        {
            u--;

            c = 0;
            d = a;

            while(d)
            {
                c = (c + (d & 1) * r) % p;
                r = (r << 1) % p;
                d >>= 1;
            }

            r = c;
        }

        u >>= 1;

        c = 0;
        d = a;
        e = a;

        while(d)
        {
            c = (c + (d & 1) * e) % p;
            e = (e << 1) % p;
            d >>= 1;
        }

        a = c;
    }

    return r;
}

int main()
{
    int n = -1;
    int a, b, p;
    int i;

    scanf("%d", &n);

    if(n < 1)
    {
        return -1;
    }

    for(i=0; i<n; i++)
    {
        scanf("%d %d %d", &a, &b, &p);

        printf("%d\n", call(a, b, p));
    }

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c89

3.运行及其结果

$ ./test
2
2 2 6
4
3 4 10
1