一.基本概念&&操作
二.常用技巧
(1) 取最右边的 1 ,适用范围“lowbit”
t=A&(-A)
lowbit的常用应用:1.快速幂 2.树状数组 3.状态压缩动规 4.大整数乘法(64位)
三.实际应用
(1).快速幂
#include<iostream> #include<cstdio> using namespace std; long long mul(long long a,long long b,long p) { long long ans=1; for(;b;b>>=1) { if(b&1)//b是否为奇数 ans=(ans*a)%p;//进行乘积操作 a=(a*a%p);//a的下传 } return ans%p;//注意在 mod p 一次 } int main(void) { long long a,b,p; scanf("%lld%lld%lld",&a,&b,&p); printf("%lld",mul(a,b,p)); return 0; }
(2).大整数乘法(64位)
#include<iostream> #include<cstdio> using namespace std; long long mul(long long a,long long b,long p) { long long ans=0; for(;b;b>>=1) { if(b&1) //判断b是否为奇数 { ans=(ans+a)%p; //累计答案 } a=a*2%p;//数值乘积 } return ans; } int main(void) { long long a,b,p; scanf("%lld%lld%lld",&a,&b,&p); printf("%lld",mul(a,b,p)); return 0; }
配套练习1 :P1582 倒水,P1469 找筷子,P3908 异或之和