题目：
大意：求A^B的所有因子的和。
思考：在纸上画一画就知道了，可以枚举A^B的第n个素因子的次方取值分别求和，由只含前n-1个素因子的因子和推出前n个，以此分治（或叫递推）。
具体做法：对A分解因式（类似欧拉函数的求法），对每个素因子p，假如是e次方，扩大b倍，然后求1+p1+p2+...+pe这个等比数列的和，其中要用到等比数列求和公式，要除以p-1这个东西，当p-1与9901互素的时候还好，但万一不互素呢？
这种情况我不会，后来才知道，其实只要把mod，即9901，乘上个p-1 以后就可以随便除以p-1了（形象地想，不一定对：也就是把整个数域扩大了p-1倍，这样p-1就成了一个单位，相当于原来的单位1，这时除以p-1也就相当于除以单位1而已……），于是问题就解决了。
可能这是数论书上的结论吧，数论概论买来还没看- -，到时候看到了再在这里补上那条结论吧（好像其实就是当d|MOD的时候，同余模运算里面可以随便除以d，当然d与MOD互素的时候直接用extgcd求逆元再乘就可以了……）。
另外注意数据范围，由于MOD乘上了一个数，中间运算可能会超int，尤其注意乘法的时候，还可能超long long！！！只能拆成二进制来边模边加着乘了至。看来像Mul(),Pow()这种函数，在数论题里面应该是必写的了，谁知道他什么时候会超范围。
标程：
#include#include #include using namespace std;typedef long long ll;const ll M = 9901;ll Mul(ll a,ll b,ll p) { a%=p; ll res=0; while(b) { if(b&1) { res+=a; if(res>p) res-=p; } a*=2,b/=2; if(a>p) a-=p; } return res;}ll Pow(ll a,ll b,ll p) { if(b==0) return 1; ll t=Pow(a,b/2,p); t=Mul(t,t,p); if(b&1) t=Mul(t,a,p); return t;}int main(){ ll a,b; while(~scanf("%lld%lld",&a,&b)) {// if(b==0) {// puts("1");// continue;// }// if(a==0) {// puts("0");// continue;// } ll ans=1; for(ll i=2;i*i<=a;i++) if(a%i==0) { ll e=0; while(a%i==0) { e++; a/=i; } e*=b; ans=Mul(ans,(Pow(i,e+1,(i-1)*M)-1)/(i-1),M); } if(a>1) { ll e=b; ans=Mul(ans,(Pow(a,e+1,(a-1)*M)-1)/(a-1),M); } printf("%lld\n",ans); } return 0;}
PS：不要怀疑。。上面那个网址就是POJ。。我无意中发现的。。不知为何，用联通宽带上这个比上poj.org快多了了，嘿嘿。。=。=。。。