poj 1845 数论（唯一分解定理+分治法求等比数列前n项的和mod m的值）

算数基本定理的运用：

思路：将a作质因数分解，然后配合快速幂和分治的思想即可。

注意：求逆元是错误的，因为不能保证互质。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 typedef long long ll;
 5 
 6 ll pow_mod( ll a, ll b, ll mod )
 7 {
 8     ll ans = 1, w = a % mod;
 9     while ( b )
10     {
11         if ( b & 1 )
12         {
13             ans = ans * w % mod;
14         }
15         b = b >> 1;
16         w = w * w % mod;
17     }
18     return ans;
19 }
20 
21 ll sum( ll p, ll q, ll mod )
22 {
23     if ( q == 0 ) 
24         return 1;
25     if ( q & 1 )
26         return sum( p, q / 2, mod ) * ( 1 + pow_mod( p, q / 2 + 1, mod ) ) % mod;
27     else
28         return ( ( 1 + pow_mod( p, q / 2, mod ) ) * sum( p, q / 2 - 1, mod ) + pow_mod( p, q, mod ) ) % mod;
29 }
30 
31 ll solve( ll a, ll b, ll mod )
32 {
33     ll ans = 1;
34     for ( int i = 2; i * i <= a; i++ )
35     {
36         if ( a % i == 0 )
37         {
38             int cnt = 0;
39             do
40             {
41                 cnt++;
42                 a = a / i;
43             } while ( a % i == 0 );
44             ans = ans * sum( i, cnt * b, mod ) % mod;
45         }
46     }
47     if ( a > 1 )
48     {
49         ans = ans * sum( a, b , mod ) % mod;
50     }
51     return ans;
52 }
53 
54 int main()
55 {
56     ll a, b;
57     while ( cin >> a >> b )
58     {
59         cout << solve( a, b, 9901 ) << endl;
60     }
61     return 0;
62 }