昨日作业讲解

64位整数乘法

这里是视频讲解：

作业视频讲解~

我们来想一下这题用类似快速幂的思路可以怎么写。

快速幂模板先奉上：

ll qmi(ll a, ll k, ll p)
{
    ll res = 1;
    while(k)
    {
        if(k & 1) res = (ll) res * a % p;
        k = k >> 1;//k >>= 1;
        a = (ll) a * a % p;
    }
    return res;
}

然后我们想一下如何用类似快速幂的思路写乘法。

我们可以把反复平方变为反复二倍。

这就是本题的思路，接下来我们模拟一组数据。

比如a = 2, k = 5, p = 5, 求2 * 5 % 5
正常结果应该是0对吧。
接下来我们反复二倍一下。

q[0] = 2 * 1 % 5 = 2;
q[1] = 2 * (1 * 2) % 5 = 2 * q[0] % 5 = 4;
q[2] = 2 * (1 * (2 ^ 2)) = 2 * q[1] % 5 = 4 * q[0] % 5 = 3;
……

5的二进制表示是101。

则：
  2 * 5 % 5
= (q[0] + q[2]) % 5
= (2 + 3) % 5
= 5 % 5
= 0
!!!!!!!!!!

最后与真实运算结果一样！

最后献上代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 100010;
ll a, k, p, res = 0;
int main()
{
    cin >> a >> k >> p;
    while(k)
    {
        if(k & 1) res = (ll)(res + a) % p;
        k >>= 1;
        a = (ll)(a * 2) % p;
    }
    cout << res << endl;
    return 0;
}

好了这期分享就到这里了。

未经允许，请问转载！

这是我的全部分享

另外，我对LeetCode的刷题活动很期待~

bye~