模运算

模运算运算规则

$$
(a + b) \mod c = (a \mod c+b \mod c) \mod c
$$
$$
(a - b) \mod c = (a \mod c+b \mod c) \mod c
$$
$$
(a \cdot b)\mod c=((a\mod c)\cdot(b\mod c)) \mod c
$$
对于除法不存在这样的公式

乘法取模
对于这个算法本人其实也并不是很吃透了，但是我这样写下来的话只是简单的记录一下我的想法
首先这是一个乘法取模即
$$
(a \cdot b)\mod c=((a\mod c)\cdot(b\mod c)) \mod c
$$
然后我们就是先对a,b单独取模，但是得到后的a,b，我们仍然无法确定它们相乘是否会越界，
所以我们对ab进行一下变形
那么a * b = a * 2 * b /2
如果展开的话那么(a * 2 * 2 * 2 … )(b/2/2/2…)
但是当进行除法的时候当b为奇数的话那么就相当于（a * 2)*(b/2 + 1) = (a * 2)(b/2) + (a * 2),多了一个
a * 2,所以我们多一个判断奇

我自己认为它的整体的想法就是把 a*b进行转化每次其实都把范围给锁定再一定范围内，以至于不会超出界限

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

LL mul(LL a, LL b,LL c)
{
a = a % c;
b = b % c;
ll res = 0;
while(b > 0)
{
    if(b & 1) res = (res + a)%c;
    a = (a + a) % c;
    b >>= 1;
}
return res;
}
int main()
{
    LL a,b,c;
    cin >> a >> b >> c;
    cout << ((a % c) *(b % c)) % c << endl;
    cout << mul(a,b,c) << endl;
    return 0;
}

快速幂

幂次与二进制的关系
任何幂都可以转化为二进制表示
幂次用二进制分解
在程序中我们只需判断那个位数是1还是0

根据分析我们其实可以发现所有的幂都是倍乘关系那么可以通过递推关系来表示

int fastPow(int a,int n)
{
    int ans = 1;
    while(n)
    {
        if(n & 1) ans *= a;
        a * = a;
        n >> 1;
    }
    return ans;
}

幂运算

typedef long long ll;
ll fastPow(ll a,ll b,ll mod)
{
 ll ans = 1;
 a % = mod;
 while(b)
 {
 if(b & 1) ans = (ans * a)%mod;
 a = (a * a)%mod;
 b >> 1;
  }
  return ans;
}