(2008个1)的(2008个1)次方 mod 2008 =?
2008个1就是 11...1 一共2008位

闲着没事自己想的题目，哈哈

把大整数拆成二进制？

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

怎么可能……，模2008的。

嗯，我知道你什么意思了，不过你写的有点问题。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");
}