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

题目链接：

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

题目大意：

求A^B的因子和

解题思路：

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

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

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

所以直接求出这个即可

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

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 typedef long long ll;
 5 const int maxn = 1000000+10;
 6 ll mul(ll a, ll b, ll m)
 7 //求a*b%m
 8 {
 9     ll ans = 0;
10     a %= m;
11     while(b)
12     {
13         if(b & 1)ans = (ans + a) % m;
14         b /= 2;
15         a = (a + a) % m;
16     }
17     return ans;
18 }
19 ll pow(ll a, ll b, ll m)
20 {
21     ll ans = 1;
22     a %= m;
23     while(b)
24     {
25         if(b & 1)ans = mul(a, ans, m);
26         b /= 2;
27         a = mul(a, a, m);
28     }
29     ans %= m;
30     return ans;
31 }
32 int main()
33 {
34     ll a, b;
35     //freopen("out.txt", "w", stdout);
36     while(cin >> a >> b)
37     {
38         ll ans = 1, t, m = 9901, mod;
39         for(ll i = 2; i * i <= a; i++)
40         {
41             if(a % i == 0)
42             {
43                 ll cnt = 0;
44                 while(a % i == 0)
45                 {
46                     a /= i;
47                     cnt++;
48                 }
49                 mod = m * (i - 1);
50                 t = (pow(i, cnt * b + 1, mod) - 1) % mod;
51                 t = (t + mod) % mod;
52                 t /= (i - 1);
53                 ans = (ans * t) % m;
54             }
55         }
56         if(a > 1)
57         {
58             mod = m * (a - 1);
59             t = (pow(a, b + 1, mod) - 1) % mod;
60             t = (t + mod) % mod;
61             t /= (a - 1);
62             ans = (ans * t) % m;
63         }
64         cout<<ans<<endl;
65     }
66     return 0;
67 }

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

推荐阅读