简单数据处理办法

最大公约数算法

#include <iostream>
using namespace std;
int fun(int n,int m){
if(m==0){
return n;
    }
return fun(m,n%m);
}
int main(){
int n,m;
cin>>n>>m;
cout<<fun(m,n%m);
return 0;
} 

优化质数

#include <iostream>
using namespace std;
int main(){
int n;
cin>>n;
for(int i = 2 ; i*i < n ; i++){
if(n%i==0){
cout<<"No";
return 0;
        }
    }
cout<<"yes";
return 0;
}  

质数段

#include <iostream>
using namespace std;
int main(){
int n,m;
cin>>n>>m;
int a[m];
for(int i = 2 ; i < m ; i++){
        a[i]=0;
    }
for(int i = 2 ; i*i < m ; i++){
if(a[i]==0){
for(int j = i*i ; j < m ; j += i){
                a[j]=1;
            }
        }
    }
for(int i = n ; i < m ; i++){
if(a[i]==0){
cout<<i<<endl;
        }
    }
return 0;
} 

快速二分幂

#include <iostream>
using namespace std;
int temp = 1;
int f(int a,int b,int mod){
if(b==0){
return 1%mod;
    }
int temp = f(a,b/2,mod);
    temp = temp * temp % mod;
if(b%2==1){
        temp = temp * a %mod;
    }
return temp;
} 
int main(){
int a,b,c;
cin>>a>>b>>c;
cout<<f(a,b,c);
return 0;
} 

快速二分幂与dfs思想

#include <iostream>
using namespace std;
int f(int a,int b,int c){
int res = 1 ; 
for(;b;b = b/2){
//cout<<b<<endl; 
if(b&1){
            res = res * a%c;
        }
        a = a * a % c;
    }
return res;
} 
int main(){
int a,b,c;
cin>>a>>b>>c;
cout<<f(a,b,c);
return 0; 
}