质数筛

普通筛

时间复杂度为0(n * sqrt(n)

#include<bits/stdc++.h>
using namespace std;
int is(int n){
if(n==1)return 0;
else{
    for(int i=2;i<=sqrt(n);i++)
    if(n%i==0)return 0;
}
return 1;}
int main(){
int n,x;
cin>>n;
while(n--){
    cin>>x;
    if(is(x))cout<<x<<" ";
}
return 0;
}

埃拉托斯特尼筛法

时间复杂度为O(nloglogn)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll maxn=1e5+5;
ll a[maxn];
void solve(){
    memset(a,1,sizeof(a));
    a[0]=a[1]=0;
for(ll i=2;i*i<=maxn;i++){
    if(a[i]){
        for(ll j=i*i;j<=maxn;j+=i){
            a[j]=0;
        }
    }
}
ll n;
cin>>n;
while(n--){
    ll x;
    cin>>x;
  if(a[x])cout<<x<<" ";
}
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    ll t;
    t=1;
  //  cin>>t;
    while(t--)solve();
    
    return 0;
}

线性筛法

时间复杂度为0(n )

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll maxn=1e5+5;
ll a[maxn];
vector<ll>is;
void solve(){
    memset(a,1,sizeof(a));
    a[0]=a[1]=0;
for(ll i=2;i<=maxn;i++){
  if(a[i])is.push_back(i);
    for(ll p:is){
        if(i*p>maxn)break;
        a[i*p]=0;
        if(i%p==0)break;
    }
}
ll n;
cin>>n;
while(n--){
    ll x;
    cin>>x;
  if(a[x])cout<<x<<" ";
}
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    ll t;
    t=1;
  //  cin>>t;
    while(t--)solve();
    
    return 0;
}

快速幂

判断b的最后一位是不是1，b >>= 1 是右移赋值运算符，等价于 b = b >> 1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
int f(ll a,ll b,ll c){
    int r=1;
    while(b){
        if(b&1){
            r=r*a%c;
        }
        a=(a*a)%c;
        b>>=1;}
    return r;
    }
int main(){
ll t,n,m,ans;
cin>>t>>n>>m;
ans=f(t,n,m);
//2^10 mod 9=7
cout<<t<<"^"<<n<<" "<<"mod "<<m<<"="<<ans<<"\n";
//cout<<f(t,n,m)<<"\n";
return 0;
}

最大公约数和最小公倍数

c++17中可以使用__gcd

#include<bits/stdc++.h>
using namespace std;
int main(){
   long long int a,b;
    cin>>a>>b;
    cout<<__gcd(a,b)<<" "<<a*b/__gcd(a,b)<<"\n";
    return 0;
}

辗转相除法求最大公约数

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}
int main(){
   long long int a,b;
    cin>>a>>b;
    cout<<gcd(a,b)<<" "<<a*b/gcd(a,b)<<"\n";
    return 0;
}

同余定理

[P8649] 蓝桥杯 2017 省 B] k 倍区间 - 洛谷

根据同余定理可以推出

余数相同的两个区间之差一定可以被k整除

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const ll MAXN = 1e5+10;
ll N,K, C[MAXN], PS[MAXN];
map<ll,ll> R;
   ll ans = 0;
void sove(){
    cin >> N >> K;
    R[0] = 1;
    for(ll i = 1; i <= N; i++){
        cin >> C[i];
        PS[i] = PS[i-1] + C[i];
        R[PS[i]%K]++;
    }
    for(auto [r,cnt] : R)
        ans += (cnt-1)*cnt/2;
    cout << ans<<"\n";
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0); 
    ll t;
    t=1;
    //cin>>t;
    while(t--)sove();
    
    return 0;
}