由题意,要求A^B的所有约数之和%9901。
A可以唯一分解成p1^a1*p2^a2*...*pn^an,
A^B=p1^(a1*B)*p2^(a2*B)*...*pn^(an*B);
A^B的所有约数之和=[1+p1+p1^2+...+p1^(a1*B)]*[1+p2+p2^2+...+p2^(a2*B)]*[1+pn+pn^2+...+pn^(an*B)].
而等比数列1+pi+pi^2+pi^3+...+pi^n可以由二分求得,思想是把式子从中间断开。
若n为奇数,一共有偶数项,设p为3,则(1+p)+(p^2+p^3)=(1+p)+p^2(1+p).
若n为偶数,一共有奇数项,设p为4,则(1+p)+p^2+(p^3+p^4)=(1+p)+p^2+p^3(1+p)。
而p^n可以二分求出。
这样两次二分就可以求出了.
CODE