POJ-1845 Sumdiv---因子和（快速幂+快速加法+因子和公式）

题目链接：

https://cn.vjudge.net/problem/POJ-1845

题目大意：

求A的因子和

解题思路：

先将A质因数分解，然后B次方的质因数指数就是乘上B即可

这里要mod9901，但是有除法，而且不一定有逆元，所以用公式：

a/b mod m 等价于 a mod (m * b) / b

所以直接求出这个即可

但是mod m*b 这个数字可能很大，就算模上之后再相乘也会溢出，所以应该用有快速加法的快速幂

 #include<iostream>

 #include<cstdio>

 using namespace std;

 typedef long long ll;

 const int maxn = +;

 ll mul(ll a, ll b, ll m)

 //求a*b%m

 {

     ll ans = ;

     a %= m;

     while(b)

     {

         if(b & )ans = (ans + a) % m;

         b /= ;

         a = (a + a) % m;

     }

     return ans;

 }

 ll pow(ll a, ll b, ll m)

 {

     ll ans = ;

     a %= m;

     while(b)

     {

         if(b & )ans = mul(a, ans, m);

         b /= ;

         a = mul(a, a, m);

     }

     ans %= m;

     return ans;

 }

 int main()

 {

     ll a, b;

     //freopen("out.txt", "w", stdout);

     while(cin >> a >> b)

     {

         ll ans = , t, m = , mod;

         for(ll i = ; i * i <= a; i++)

         {

             if(a % i == )

             {

                 ll cnt = ;

                 while(a % i == )

                 {

                     a /= i;

                     cnt++;

                 }

                 mod = m * (i - );

                 t = (pow(i, cnt * b + , mod) - ) % mod;

                 t = (t + mod) % mod;

                 t /= (i - );

                 ans = (ans * t) % m;

             }

         }

         if(a > )

         {

             mod = m * (a - );

             t = (pow(a, b + , mod) - ) % mod;

             t = (t + mod) % mod;

             t /= (a - );

             ans = (ans * t) % m;

         }

         cout<<ans<<endl;

     }

     return ;

 }