1.快速幂
位运算
1 long long ksm(int n,int x){2 int ans=1;3 while(x){4 if(x&1){5 ans*=n;6 }7 n*=n;8 x>>=1;9 } 10 return ans; 11 }
递归
1 long long ksm(int n,int x){2 if(x==0) 3 return 1;4 else if (n%2==1){5 return ksm(n,x-1)*n;6 }7 else{8 int temp=ksm(n,x/2);9 return temp*temp; 10 } 11 }
2.并查集
1 #include <bits/stdc++.h> 2 using namespace std; 3 int n,m; 4 int fa[100000]; 5 6 void init(){ 7 for(int i=0;i<n;i++){ 8 fa[i]=i; 9 } 10 } 11 12 int find(int x){ 13 if(fa[x]==x){ 14 return x; 15 } 16 else{ 17 fa[x]=find(fa[x]); 18 return fa[x]; 19 } 20 } 21 22 void unionn(int x,int y){ 23 fa[find(x)]=find(y); 24 return ; 25 }
3.求最大公约数
懒了,这是辗转相除
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int a,b,c; 5 6 int gcd(){ 7 if(a<b){ 8 c=a; 9 a=b; 10 b=c; 11 } 12 while(b!=0){ 13 c=b; 14 b=a%b; 15 a=c; 16 } 17 return a; 18 }
4.二进制转十进制,十进制转二进制
二转十
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 long long num,m,i=0,sum=0; 5 6 void print(){ 7 cout<<sum; 8 return ; 9 } 10 11 void twototen(){ 12 while(num!=0){ 13 m=num%10; 14 num/=10; 15 sum+=m*pow(2,i); 16 i++; 17 } 18 print(); 19 return ; 20 }
十转二
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 long long num,m,i=0,n=2; 5 int a[32]; 6 7 void print(){ 8 for(i--;i>=0;i--){ 9 cout<<a[i]; 10 } 11 return ; 12 } 13 14 void tentotwo(){15 while(num>0){ 16 m=num%n; 17 a[i]=m; 18 num=num/n; 19 i++; 20 } 21 print(); 22 return ; 23 }