问题标题: 除法逆元

除法逆元，费马小定理

除法逆元是费马小定理的推论

费马小定理　　b ^ (m - 1) % m = 1 % m
可以拆成　　   b * b (m - 2) % m

那么　　　　　a / b = a / b * b * b(m - 2) = a * b(m - 2) % m

鄙校的oj

https://ac.2333.moe/Problem/view.xhtml?id=1614

下面是代码实现

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <algorithm>
 5 using namespace std;
 6 const int Max = 1e5 + 10;
 7 __int64 Mod = 1e9 + 7;
 8 char str[Max];
 9 __int64 Pow(__int64 k, __int64 a)    //    快速幂求a^k(a的k次方)
10 {
11     __int64 sum = 1;
12     __int64 base = a;
13     while(k > 0)
14     {
15         if(k & 1)
16             sum = sum * base % Mod;        
17         base = base * base % Mod;
18         k = k >> 1;
19     }
20     return sum;
21 }
22 int main()
23 {
24     __int64 k;
25     int i;
26     while(cin >> str >> k)
27     {
28         __int64 sum = 0;
29         int len = strlen(str);        
30         for(i = 0; i < len; i++)
31         {
32             if(str[i] == '0' || str[i] == '5')
33             {
34                 __int64 cnt = ((Pow(len, 2) - 1) % Mod + Mod) % Mod;
35                 __int64 a = ((Pow(i + len * k, 2) - Pow(i, 2)) % Mod + Mod) % Mod;    //之所以加Mod后再取模，是怕前面的数是负数，这里是重点
36                 __int64 b = Pow(Mod - 2, cnt) % Mod;    // 前n项和sn = a / b; a = an * q - a1; b = q -1;
37                 sum = (sum + a * b % Mod ) % Mod;    // a / b % Mod = a * Pow(Mod - 2, b) % Mod这是除法逆元
38             }
39         }            
40         printf("%I64d\n", sum);
41     }
42     return 0;
43 }