快速幂，位运算，pow()函数

位运算：

位运算可以用来查找01二进制串中1或0的个数，同时也可以实现幂的计算，但是只能是以2为底的幂运算

统计字符串中1的个数

#include<bits/stdc++.h>
using namespace std;
string T;
int main()
{
	cin>>T;
	int count=0;
	cout<<T.length()<<endl; 
	for(int i=T.length()-1;i>=0;i--){
		if((T[i]-'0')&1) count++;
	}
	cout<<count<<endl;
	return 0;
}

求a的b次方对p取模（1<=a,b,p<=10^9)（快速幂）时间复杂度：o(log(b))

#include<bits/stdc++.h>
using namespace std;
int a,b,p;
int main(){
	cin>>a>>b>>p;
	long long sum=1;
	for(;b>0;b=b>>1){
		if(b&1) sum=(sum*a)%p;
		a=(a*a)%p;
		cout<<a<<" "<<b<<endl;
	}
	cout<<sum<<endl;
	return 0;
}

求a*b对p取模，1<=a,b,c<=10^18(快速幂）

#include<bits/stdc++.h>
using namespace std;
int a,b,p;
int main(){
	cin>>a>>b>>p;
	long long sum=0;
	for(;b>0;b=b>>1){
		if(b&1) sum=(sum+a)%p;
		a=(a*2)%p;
		cout<<a<<" "<<b<<endl;
	}
	cout<<sum<<endl;
	return 0;
}

 pow函数的时间复杂度为，快速幂时间复杂度为o（logn）。当我们遇到比较多次数使用pow函数时，可能为导致时间花销比较长，会T，这时候我们可以用位运算来代替pow函数，但是当数据量比较大时，位运算可能也会超时。这是我们可以用一个qw数组，qw[i]表示以某个数X为底，X^i；下面以二进制为例

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int a,b,p;
int qw[N]={1};
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		qw[i]=qw[i-1]<<1;
	}
	for(int i=0;i<=n;i++){
		cout<<"i: "<<i<<" "<<qw[i]<<endl;
	}
	return 0;
}

tips：有些时候题目输出数据量很大，这是可能会在输出卡时间，我们一般使用的cout花费时长比printf （）花费时长要长，且数据量越多越明显，我们可以有两种解决办法：

1.使用printf()代替cout。printf()用法：printf("<格式化字符串>", <参量表>)。

#include<bits/stdc++.h>
using namespace std;
const int N=1000;
int a,b,p;
int qw[N]={1};
int main(){
	printf("%d\n",26);
	printf("%d",26);
	puts("");
	printf("%4d",14);//4d表示输出宽度，14的宽度为2，所以就会在14左边补两个宽度的空格。 
	printf("%-4d",14);//输出宽度为4，如果比实际数值宽度大，多出的宽度会在右边用空格填补 
	puts("");
	printf("%.7f",2.102938432947223810832047204);//.7f表示小数点保留到7位. 
	return 0;
}

2.在代码中加上：ios::sync_with_stdio(false)，这样cou和printf的速度是一样的，缺点就是加了这句话之后，你的代码块中只能使用cout或者printf，两者不能交替使用。