题目大意： 给出n，k，s为2008的n次幂的所有因子和，m为s%k，求2008的m次幂%k 分析： 2008 = 2^3 * 251; 故 2008 ^ n = 2 ^ 3n * 251 ^ n; 设集合C= {2^0 , 2^1 , …… ， 2^3n}; sum(C) = 2^(3n+1) - 1; 集合W = {251^0 , 251^1 , …… ,251^n}； sum(W) = (251^(n+1) - 1 )/250; 则所有因子和为： S = sum(C) * sum (W); 因为S太，故直接取模； S = sum(C) * sum(W) % K; 因为 sum(W)存在除法 ， 所以需要对K* 250 取模； 故 S = sum(C) * sum(W) %( K*250)  /250; N^M % mod 的求法： long long Pow(long long n ,long long m, int mod)
{
    long long res = 1;
    while(m >= 1)
    {
        if(m & 1)
        {
            res = (res * n ) % mod;
        }
        n = n * n % mod ;
        m >>= 1;
    }
    return res;
}

#include #include #include #include #include #include #include #include using namespace std; #define MOD 3780 long long Pow(long long n ,long long m, int mod) { long long res = 1; while(m >= 1) { if(m & 1) { res = (res * n ) % mod; } n = n * n % mod ; m >>= 1; } return res; } int main() { int N , K; while(cin >> N >> K && ( N || K)) { long long temp1 , temp2; temp1 = Pow(2 , 3 * N + 1 , K * 250) - 1; temp2 = Pow(251 , N + 1 , K * 250) - 1; long long res = (temp1 * temp2) % (250 * K); res /= 250 ; res = Pow(2008 , res , K); cout << res <