YBT 1633：【例 3】Sumdiv

http://ybt.ssoier.cn:8088/problem_show.php?pid=1633

A^B

快速幂求结果，所有约数和，可以通过组合来进行得到。

技巧，通过递归得到1~n次的和.sum(n/2)*(1+？)这半，通过加自身和，调整后的自身以及补位，在log的时间内算出所有结果.

分解质因数，可以预先用素数，也可以奇偶法剪枝。

 1 #include
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=9901;
 5 ll a,b,cnt;
 6 const int N=1e5+520;
 7 ll prime[N],n[N];
 8 ll qmi(ll x,ll y)
 9 {
10     ll ans=1;
11     while(y)
12     {
13         if(y&1) ans=ans%mod*x%mod;
14         y>>=1;
15         x=x*x%mod;
16     }
17     return ans;
18 }
19 ll sum(ll p, ll k)//递归法求n次和。 
20 {
21     if(k==0) return 1;
22     if(k&1) return (sum(p,k/2)*(1+qmi(p,k/2+1)))%mod;
23     else return (sum(p,k/2-1)*(1+qmi(p,k/2+1))+qmi(p,k/2))%mod;
24 }
25 void solve(ll a,ll b)
26 {
27     for(int i=2;i<=sqrt(a);)
28     {
29         if(a%i==0)
30         {
31             prime[++cnt]=i;
32             n[cnt]=0;
33             while(!(a%i)) n[cnt]++,a/=i;
34         }
35         if(i==2) i++;//奇偶法，或者筛选出来素数直接用 
36         else i+=2;
37     }
38     if(a!=1) prime[++cnt]=a,n[cnt]=1;
39     ll ans=1;
40     for(int i=1;i<=cnt;i++)
41     {
42         ans=(ans*(sum(prime[i],n[i]*b))%mod)%mod;
43       }  
44     cout<'\n';
45 }
46 int main()
47 {
48     scanf("%lld%lld",&a,&b);
49     solve(a,b);
50     return 0;
51 }