龟速乘
龟速乘这个技巧和它的名字一样，时间复杂度为 。明明能直接算乘法，还要来个龟速~不过慢工出细活，结合上篇提到的[[费马小定理]]定理，可以解决两数直接相乘再取模可能导致的数据溢出。这个方法与[[快速幂]]有异曲同工之妙。 例：求b乘q的值并对k取模
CPP
12345678910111213141516171819#include <iostream>
#include <cmath>
#define ll long long
using namespace std;
int main ()
{
ll b,p,k;
cin>>b>>p>>k;
ll ans=0;
while (p){
if (p&1){
ans=(ans+b)%k;
}
b=b*2%k;
p=p>>1;
}
cout<<ans<<endl;
}