【HDU1852】Beijing 2008

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1852
题意：给出n、k，令m=$2008^n$所有因子的和%k，输出$2008^m \mod k$。
题解：
求$x^y$的因数和
将$x^y$唯一分解

$$x^y=\prod_{i=1}^{k}p_{i}^{e_{i}\times y}$$
对于任意一个质因数 $p_{i}$， $p_{i}^{e_{i}}$对于答案的贡献是
$$S_{i}=\sum_{j=0}^{e_{i}\times y}p_{i}^j$$
这可以看成一个等比数列求和，化简为
$$S_{i}= \frac {p_{i}^{e_{i} \times y+1}-1}{p_{i}-1}$$
所有约数的和应该为所有 $S_{i}的积$
即 $$S=\prod_{i=1}^{k} S_{i}=\prod_{i=1}^{k}\frac {p_{i}^{e_{i} \times y+1}-1}{p_{i}-1}$$

对于本题，$2008=251\times 2^3$
直接可以得到 $S=\frac {(2^{3n+1}-1)(251^{n+1}-1)}{250}$
因为250和k不一定互质，所以不能求逆元
而k很小，所以我们可以将k乘以250，然后再mod，最后结果一定可以整除250。

$\frac {S}{250} \mod k=\frac {S\mod (250*k)}{250}$
然后写个快速幂就OK了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
LL n,m,k,t;LL ksm(LL a,LL b,LL mod)
{int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1; }return ans % mod;
}LL calc(LL x,LL mod)
{LL a=ksm(2,3*x+1,250*mod);LL b=ksm(251,x+1,250*mod);return ((a-1)*(b-1)/250)%mod;
}int main()
{while(scanf("%lld%lld",&n,&k)&&(n||k)){m=calc(n,k);printf("%lld\n",ksm(2008,m,k)); }return 0;
}