龟速乘与快速幂
n&1: 取n的二进制最末位
n>>1: 右移一位，相当于去掉n的二进制最末尾（相当于n/2）
n<<1 相当于n*2
if(n%2==1) 可以写成if((n&1)==1)或if(n&1)
位运算比 +-*/ 更快
龟速乘
求 $ (a\times b) \bmod p$。
例：
\((7 \times 3) \bmod 5\)
\(7=1+2+4\)
\(7 \times 3=(1+2+4) \times 3=(2^0+2^1+2^2) \times 3\)
\(\hspace{0.87cm}=3+6+12\)
\(7 \times 3 \bmod 5=(3 \bmod 5)+(6 \bmod 5)+(12 \bmod 5)\)
取 b 末尾二进制，如果是 1 就把 ans 加上 a，如果不是就不加。
ans 取余 p。
因为每往前一位二进制就乘 2，所以 a 也乘 2。
随后 b 除以 2。
Luogu P10446 64位整数乘法
#include<iostream>
#define int long long
using namespace std;
int a,b,p,ans;
signed main(){cin>>a>>b>>p;while(b){if(b&1){ans+=a;ans%=p;} a<<=1;a%=p;b>>=1;}cout<<ans;return 0;
}
快速幂
求 \(a^n \bmod p\)。
求 \(a^{19}\)：
\(19=16+2+1=2^4+2^1+2^0\)
\(a^{19}=a \times a^2 \times a^{16}\)
与龟速乘同理，把加改成乘，\(ans\) 初值为 \(1\)，结束。
严谨起见，要特判 \(ans=0\) 的情况。
#include<iostream>
#include<cstdio>
using namespace std;
int a,b,p;
long long ans;
long long ksm(int a,int b,int p){long long ans=1,tmp=a;while(b>0){if(b&1) ans=ans*tmp%p;tmp=tmp*tmp%p;b>>=1;}return ans;
}
int main(){cin>>a>>b>>p;ans=ksm(a,b,p);if(a==1&&b==0&&p==1) ans=0;printf("%d^%d mod %d=%d",a,b,p,ans);return 0;
}
Luogu P1965 [NOIP2013 提高组] 转圈游戏
求出公式：
\(ans=(x+((10^k \bmod n) \times m) \bmod n) \bmod n\)
用快速幂求出 \(10^k \bmod n\) 然后套公式计算。
#include<iostream>
#define int long long
using namespace std;
int n,m,k,x;
int kuai,ans;
long long ksm(int a,int b,int p){long long ans=1,tmp=a;while(b>0){if(b&1) ans=ans*tmp%p;tmp=tmp*tmp%p;b>>=1;}return ans;
}
signed main(){cin>>n>>m>>k>>x;kuai=ksm(10,k,n);ans=(x+(kuai*m)%n)%n;cout<<ans;return 0;
}