不对
10#我的想法错了,当我没说

a^b mod k里，只要k是小整数，那就不难了
b要变为二进制，感觉会好做些。。。
若依然要用10进制的话就多加一个两大数乘法啰。。。

直接把大整数b变成二进制相当耗时啊，奇偶性好判断，但要做log(2008个1)/log2次的大整数除以2的除法运算，保守的估计大约为2008/3*10=6693次，除法运算是O(length)级别的

这个我知道啊，化为二进制的确好算一些，
但花费时间会比较多（但绝对不是楼上所写的那么多，不需要除以2啊，直接除以2^20，后面直接用移位，省了一个数量级）

直接用10进制的话就麻烦一些，加个大数乘法算10次方再取余数

这个结果要几百万位了，怎么输出？

怎么可能……，模2008的。

看错了，是次方，

想到了，不需要大数乘法，直接用10进制也没有问题，
a^b mod k
log(b)的时间复杂度

a=(a mod k)
c=1,s=0
while b>0
    d=c
    for n=1 to 5
        d=(d*c mod k)
    c=(d*d mod k)
    s = (s + c*(b mod 10)) mod k
    b = b / 10
output s
应该是这样了

[[it] 本帖最后由 雨中飞燕 于 2008-1-31 23:35 编辑 [/it]]

嗯，我知道你什么意思了，不过你写的有点问题。s不应该是累加应该是累乘。

int modExp_bigint(a,b,k)
{
    int res=1;
    int y=a mod k;// O( length(a) )
    while(b>0){ //O( length(b) )
        r=b mod 10; //如果b是按照10进制存储 ，这里只需取一位 O(1)
        res=res*modExp_int(y,r,k) mod k; //O(log r)<O(log10)=O(1)
        y=modExp_int(y,10,k); //O(log10)=O(1)
        b/=10;  //如果b是按照10进制存储 ，这里只需移动指针 O(1)
    }
    return res;
}

效率确实不错。
我想这道题的时候是刚看完欧拉定理，a^ф(m)=1 (mod m)
所以可以让a=a mod m, b= b mod ф(m)，这样就变成整数的幂模运算了，
ф(2008)=1000
刚好b直接等于111就可以了
下面modExp2008是按飞燕想法写的， modExp2008v2是用欧拉定理做的。

#include <iostream>
using namespace std;

int modExp_int(int a,int b,int m)
{
    int t=1,y=a%m;
    while(b){
        if(b&1){
            t=t*y%m;
        }
        y=y*y%m;
        b=(b>>1);
    }
    return t;
}

int modExp2008()
{
    int res=1,y=0;
    for(int i=0;i<2008;i++){
        y=(y*10+1)%2008;
    }
    for(int i=0;i<2008;i++){
        res=res*modExp_int(y,1,2008)%2008;
        y=modExp_int(y,10,2008);
    }
    return res;
}

int modExp2008v2()
{
    int a=0;
    for(int i=0;i<2008;i++){
        a=(a*10+1)%2008;
    }
    return modExp_int(a,111,2008);
}    


int main()
{
    printf("%d\n",modExp2008());
    printf("%d\n",modExp2008v2());    
    system("pause");
} 

初看题目，觉得是来搞怪的
再看题目，觉得又点意思，
想做题目时，发现很困难，
很不错的说，  
答案我收下了，有空研究研究