为了打篮球杯而捡起来之前学的oi
TA？那是什么东西，能吃吗？
/其实是感觉这行现状一般前景惨淡想着我还年轻趁早跑路比较好
本篇大概是位运算专题，之后以位运算为主的题目基本都会放在这里吧 主要以题目为主，大概不会出单独章节讲知识
1.求a^b%p,ab均小于1e9
直接一个个乘的话时间复杂度是O(b)
考虑位运算，任何一个自然数可以用多个2的n次方相加得到 例如10011,可以表示为\(2^0*1+ 2^1*1+2^3*0+2^4*0+2^5*1\)
如果b可以转化为一个k位的二进制数，然后a^b就可以表示为\(a*2^{k-1}*c_{k-1}*a*2^{k-2}*c_{k-2}+....*a*2^0*c_0\),其中c为0或1
每次都进行b>>1的操作，并进行b&1的判断。由于&是按位进行，所以可以判断最后一位是否是1.若是1则更新答案。并且每次循环都需要更新要乘的a值，比如如果是1011，要乘的a值则分别为a，a^2 以及a^8
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,p;//求a的b次方对p取模
ll ans=1;
int main()
{
cin>>a>>b>>p;
for(;b;b>>=1)
{
if(b&1) ans=ans*a%p;
a=a*a%p;//如果末位是0则不更新ans。
}
printf("%ld",ans);
return 0;
}
2.64位整除乘法，求a*b%p
和上题思路类似，由幂变成了相乘，原本更新ans式子里的相乘变成相加，ans初值改为0即可
点击查看代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a,b,p;
ll ans=0;
int main()
{
scanf("%ld%ld%ld",&a,&b,&p);
for(;b;b>>=1)
{
if(b&1) ans=ans+a%p;
a=a+a%p;//如果末位是0则不更新ans。
}
printf("%ld",ans);
return 0;
}