下面这个算法非常的漂亮，我把它引用过来。
来源 [url]http://bbs.pfan.cn/post-345989.html[/url]

[quote]typedef unsigned long long T;

T MyPlus( T a, T b, T c ) // (a+b)%c
{
    if(a+b>=a) return (a+b)%c; // 不溢出
    return (a%c+b%c-c);
}

T MyMultiplies( T a, T b, T c ) // (a*b)%c
{
    if(a*b/a==b) return (a*b)%c; // 不溢出

    T s = 0;
    for( T t=a; b; t=MyPlus(t,t,c),b>>=1 )
    {
        if( (b&1) != 0 )
            s = MyPlus(s,t,c);
    }
    return s;
}

T MyPower( T a, T b, T c ) // (a^b)%c
{
    T s = 1;
    for( T t=a; b; t=MyMultiplies(t,t,c),b>>=1 )
    {
        if( (b&1) != 0 )
            s = MyMultiplies(s,t,c);
    }
    return s;
}
 [/quote]