HDU 1852 - Beijing 2008 (模除法)
题意
求$2008^K$的因子和。
思路
和以前一样，不过这次不能用逆元算。得用$a / b (\bmod C) = a \bmod (b*C) / b$
代码
LL Quick_Mod(LL a, LL m, LL n)
{
LL ret = 1;
while (m)
{
if (m & 1) ret = ret * a % n;
a = a * a % n;
m >>= 1;
}
return ret;
}
int main()
{
LL N, K;
while (cin >> N >> K, N && K)
{
K *= 250;
LL M = (Quick_Mod(2, 3*N+1, K) - 1) * (Quick_Mod(251, N+1, K) - 1);
M = (M%K + K) % K / 250;
K /= 250;
cout << Quick_Mod(2008, M, K) << endl;
}
return 0;
}