数论基础算法

质数

判断质数

• 时间复杂度 \(O(\sqrt n)\)

bool is_prime(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0)return false;
    }
    return true;
}

分解质因数

• 时间复杂度 最佳\(O(\log n)\) 最坏 \(O(\sqrt n)\)

void divide(int x){
    for(int i=2;i<= x/i;i++){
        if(x%i == 0){
            int t = 0;
            while(x%i == 0){
                x/=i;
                ++s;
            }
            //质因数 次数
            printf("%d %d\n",i,t);
        }
    }
    if(x > 1)printf("%d %d\n",x , 1);
}

筛质数

• 时间复杂度 \(O(n \log \log n)\)

bool p[N];
int prime[N],cnt;
int s(int n){
    for(int i=2;i<=n;i++){
        if(!p[i]){
            prime[cnt++] = i;
            for(int j=i+i; j <= n;j+=i)p[j] = true;
        }
    }
}

• 时间复杂度 \(O(n\log \log n)\)

bool p[N];
int prime[N],cnt;
bool ai(int n){
    for(int i=2;i <= n;i++){
        if(!p[i]) prime[cnt++] = i;
        for(int j =0 ; prime[j] <= n/i; j++){
            p[prime[j]*i] = true;
            //i%prime[j]==0  -> prime[j]一定是i的最小质因子
            if(i % prime[j] == 0)break;
        }
    }
}

约数

所有约数

• 时间复杂度 \(O(\sqrt{n}+\log{n}\log{\log{n}})\)

vector diver(int x){
    vector ans;
    for(int i=1;i<= x/i;i++){
        if(x%i == 0){
            ans.push_back(i);
            if(i != x/i)ans.push_back(x/i);
        }
    }
    sort(ans.begin(), ans.end());
    return ans;
}

约数个数

• 时间复杂度 最坏 \(O(\sqrt n)\) 最佳 \(O(\log n)\)

int diver_cnt(int x){
    int res = 1;
    for(int i=2;i<=x;i++){
        if(x%i == 0){
            int alpha=0;
            while(x%i ==0){
                x/=i;
                alpha++;
            }
            res*= (alpha+1);
        }
    }
    if(x>1)res*=2;
    return res;
}

约数之和

typedef unsigned long long ULL;
const int mod = 100007;
ULL diver_sum(int x){
    ULL res = 1;
    for(int i=2;i<=x;i++){
        if(x%i == 0){
            int alpha=0;
            while(x%i ==0){
                x/=i;
                alpha++;
            }
            //秦九昭算法 1+q+..+q^n = 1+q(1+q(...))
            ULL t = 1
            for(int j =0;j1)res = res*(x+1)%mod;
    return res;
}

最大公约数与最小公倍数

// 最大公约数
int gcd(int a, int b){
    return b? gcd(b,a%b):a;
}

//最小公倍数
int lcm(int a, int b){
    return a*b/gcd(a,b);
}

快速幂

• 时间复杂度 \(O(\log k)\) \(k:幂\)

typedef long long LL;
// a^k % p
LL quick_pow(int a, int k, int p){
    int res = 1;
    while(k){
        if(k & 1) res = (LL)res*a % p;
        k>>=1;
        a = (LL) a*a % p;
    }
    return res;
}

快速积

• 时间复杂度 \(O(\log n)\) \(n: 乘积项的任意一个\)

typedef unsigned long long ULL;
// a*b % p
ULL quick_add(ULL a, ULL b, ULL p){
    ULL res = 0;
    while(b){
        if(b & 1)r = (r + a)%p;
        b >>= 1;
        a = a*2 % p;
    }
    return res;
}

求组合数算法

递推公式法

• 时间复杂度 \(O(n^2)\)

const int mod = 1e9+7;
int C[N][N];//C[a][b]
void init(){
    for(int i=0;i

typedef long long LL;
const int mod = 1e9+7;//模是质数
int fact[N],infact[N];

int quick_pow(int a,int k, int p);
void init(){
    fact[0] = infact[0] = 1;
    for(int i=1;i

#include
using namespace std;
const int N = 1010;

// p 序列 f[i] 以第i个数为结尾的最长上升子序列的长度
int p[N],f[N];

int main(){
    int n;
    cin>>n;
    for(int i =1;i<=n;i++){
        cin>>p[i];
    }
    //初始化
    for(int i = 1;i<=n;i++)f[i] = 1;
    for(int i = 2;i <= n;i++){
        for(int j = 1;j

#include
#include
using namespace std;
const int N = 100010;
int p[N],f[N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i>p[i];
    int cnt = 1;
    f[0] = p[0];
    for(int i = 1;i

#include
using namespace std;
const int N = 1010;
char A[N],B[N];
int f[N][N];
int main(){
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++)cin>>A[i];
    for(int j = 1;j<=m;j++)cin>>B[j];
    
    // 分类 ： 序列末尾是A[i]\是B[j]\是A[i]和B[j]\都不是
    for(int i = 1;i<=n;i++)
        for(int j = 1;j<=m;j++)
            if(A[i] == B[j])f[i][j] = f[i-1][j-1]+1;
            else{
                f[i][j] = max(max(f[i-1][j],f[i-1][j-1]),f[i][j-1]);
            }
    cout<

#include
using namespace std;
const int N = 1010;
int dp[N],w[N],v[N];

int slove(int n, int mv){
    for(int i = 1; i<= n; i++){
        for(int j = mv;j>=v[i];j--){
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    return dp[mv];
}

int main(){
    int n,mv;
    cin>>n>>mv;
    for(int i = 1;i<=n;i++)cin>>v[i]>>w[i];
    cout<

#include
using namespace std;
const int N = 1010;

int dp[N],w[N],v[N];

int main(){
    int n,mv;
    cin>>n>>mv;
    for(int i = 1; i<=n ; i++)cin>>v[i]>>w[i];
    
    for(int i = 1;i<=n;i++)
        for(int j = v[i];j<=mv;j++)
            dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    
    cout<

#include
using namespace std;
const int N = 100010;
int dp[N],w[N],v[N];

int main(){
    int n,mv,idx=0;
    cin>>n>>mv;
    for(int i = 1;i<=n;i++){
        int a,b,s;
        cin>>a>>b>>s;
        int d = 1;
        while(s>=d){
            idx++;
            w[idx] = b*d;
            v[idx] = a*d;
            s-=d;
            d*=2;
        }
        if(s>0){
            idx++;
            w[idx] = b*s;
            v[idx] = a*s;
        }
    }
    
    for(int i = 1;i<=idx;i++)for(int j = mv;j>=v[i];j--)dp[j] = max(dp[j],dp[j-v[i]]+w[i]);
    cout<

#include 

using namespace std;

const int N = 1010, M = 20010;

int n, m;
int v[N], w[N], s[N];
int f[2][M];
int q[M];

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n; ++ i)
    {
        for (int r = 0; r < v[i]; ++ r)
        {
            int hh = 0, tt = -1;
            for (int j = r; j <= m; j += v[i])
            {
                while (hh <= tt && j - q[hh] > s[i] * v[i]) hh ++ ;
                while (hh <= tt && f[(i - 1) & 1][q[tt]] + (j - q[tt]) / v[i] * w[i] <= f[(i - 1) & 1][j]) -- tt;
                q[ ++ tt] = j;
                f[i & 1][j] = f[(i - 1) & 1][q[hh]] + (j - q[hh]) / v[i] * w[i];
            }
        }
    }
    cout << f[n & 1][m] << endl;
    return 0;
}

#include
using namespace std;
const int N = 150;
int dp[N],v[N][N],w[N][N],s[N];

int slove(int n, int mv){
    for(int i = 1;i<=n;i++)
        for(int j = mv; j>=0; j--)
            for(int k = 0;k<=s[i];k++)
                if(j>=v[i][k])dp[j] = max(dp[j-v[i][k]]+w[i][k], dp[j]);
    return dp[mv];
}
int main(){
    int n,mv;
    cin>>n>>mv;
    for(int i =1;i<=n;i++){
        cin>>s[i];
        for(int j = 1;j<=s[i];j++){
            cin>>v[i][j]>>w[i][j];
        }
    }
    slove(n,mv);
    cout<

[a,b]间满足性质K的数的个数 -> G(x)是 [s,x]间满足性质K的数的个数 [a,b] = G(b) - G(a-1)
cnt G( x ) :
	将x拆分为每一位
	
	统计性质

	返回个数
	return cnt