快速幂

  1. ll ksm(ll a,ll b,ll mod){ //为了保险，都定义成long long
  2.     //a底数，b次数，mod取模
  3.     ll res = 1;
  4.     while(b){
  5.         if(b&1) res = res*a%mod;
  6.         a = a*a%mod;
  7.         b>>=1;
  8.     }
  9.     return res;
  10. }

矩阵快速幂

const ll mod = 1e9+7;
ll N;//第多少项
ll f = 2;//矩阵的阶数
struct node{
    ll M[2][2];
};

node mul(node a,node b){ //矩阵乘法
    node res;
    memset(res.M,0,sizeof(res.M));
    for(int i = 0;i<f;i++){ //f为矩阵的阶数
        for(int j =0;j<f;j++){
            for(int k =0;k<f;k++){
                res.M[i][j] = (res.M[i][j] + a.M[i][k]*b.M[k][j]%mod)%mod;
            }
        }
    }
    return res;
}

node ksm(node a,ll b){ //矩阵的快速幂
    node res;
    memset(res.M,0,sizeof(res.M));
    for(int i = 0;i<f;i++) res.M[i][i] = 1;
    while(b){
        if(b&1) res = mul(res,a);
        a = mul(a,a);
        b>>=1;
    }
    return res;
}

int main(){
    cin>>N;
    if(N == 0) cout<<1<<endl;
    else{
        node A = {{{3,1}, //构造系数矩阵和第一项矩阵
                   {1,3}}};
        node n0 = {{{1,0},
                    {0,0}}};
        node res = mul(ksm(A,N),n0);
        cout<<res.M[0][0]<<endl;
    }
}

线性素数筛法

#include <iostream>
using namespace std;
const int maxn = 1e6+10;

int N;
int primes[maxn],idx;//保存素数
bool st[maxn]; //素数标记，0素数，1合数
void init(){
    for(int i =2;i<=N;i++){
        if(!st[i]) primes[idx++] = i;
        for(int j = 0;primes[j]*i <=N;j++){
            st[primes[j]*i] = true;   //无论是否i%primes[j] == 0，primes[j]都是i*primes[j]的最小质因数
                                     //所以可见都是被最小质因数所筛掉的
            if(i%primes[j] == 0) break; //此时应该结束了，因为t = primes[j]是i的最小质因数，若再进行枚举，primes[j]
                                        //就不在是primes[j]*i的最小质因数了,最小质因数是t
        }
    }
}

欧拉函数

image.png
image.png

int oula(int x){
    int res = N;
    for(int i = 2;i<=x/i;i++){ //一边分解因子，一边迭代计算欧拉函数公式
        if(x%i == 0){
            res = res/i*(i-1);
            while(x%i ==0) x/=i;
        }
    }
    if(x>1) res = res/x*(x-1);
    return res;
}

线性素数筛法求欧拉函数

//此算法在我的手稿上有笔记
#include <iostream>
using namespace std;
const int maxn = 1e6+10;
typedef long long ll;

int N;
int phi[maxn];//保存每个欧拉函数的值
int p[maxn],idx;//保存质数
bool st[maxn];//0质数，1合数

void init(){
    phi[1] = 1;
    for(int i = 2;i<=N;i++){
        if(!st[i]) p[idx++] = i,phi[i] = i-1; 
        for(int j = 0;p[j]*i<=N;j++){
            st[p[j]*i] = true;
            if(i%p[j] == 0){ //p[j]是i的质因数
                phi[p[j]*i] = p[j]*phi[i]; //p[j]*i 和 i的质因数相同,所以phi[i]只需乘以一个p[j]就是p[j]*i的欧拉函数值
                break;
            }else{  //p[j]不是i的质因数
                phi[p[j]*i] = phi[i]*(p[j]-1); //p[j]*phi[i]*(1-1/p[j]) 
            }
        }
    }
}

欧拉定理

若a与n互质，则a^f(x) = 1 (mod n) f(x) 为欧拉函数

快速幂求逆元

#include <iostream>
using namespace std;
typedef long long ll;

int T,a,p;

ll ksm(ll a,ll b,ll mod){
    ll res = 1;
    while(b){
        if(b&1) res = res*a%mod;
        a = a*a%mod;
        b>>=1;
    }
    return res;
}
//根据费马小定理,a^(p-1) = 1 (mod n) n与p互质，所以a * a^(p-2) = 1 (mod n)
//所以a^(p-2) 为a关于n都逆元
int main(){
    cin>>T;
    while(T--){
        cin>>a>>p;
        if(a%p == 0) cout<<"impossible\n";
        else cout<<ksm(a,p-2,p)<<endl; 
    }
    return 0;
}

扩展欧几里得

给定a,b 求ax+by = gcd(a,b)中的系数x,y

#include <iostream>
using namespace std;
typedef long long ll;
ll T,a,b,d,x,y;

void exgcd(ll a,ll b,ll d,ll &x,ll &y){
    if(!b) d = a,x = 1,y = 0;
    else{
        exgcd(b,a%b,d,x,y);
        ll tmpx = x;
        x = y;
        y = tmpx-(a/b)*y;
    }
}

int main(){
    cin>>T;
    while(T--){
        scanf("%lld%lld",&a,&b);
        exgcd(a,b,d,x,y);
        printf("%lld %lld\n",x,y);
    }

    return 0;
}

高精度加减乘除取余

struct BigInt
{
    static const int M = 1000;
    int num[M + 10], len;

    BigInt(int x) {
        clean();
        itoBig(x);
    }
    BigInt() {
        clean();
    }

    void clean(){
        memset(num, 0, sizeof(num));
        len = 1;
    }

    void read(){
        char str[M + 10];
        scanf("%s", str);
        len = strlen(str);
        FOR(i, 1, len)
            num[i] = str[len - i] - '0';
    }

    void write(){
        _FOR(i, len, 1)
            printf("%d", num[i]);
        //puts("");
    }

    void itoBig(int x){
        clean();
        while(x != 0){
            num[len++] = x % 10;
            x /= 10;
        }
        if(len != 1) len--;
    }

    bool operator < (const BigInt &cmp) const {
        if(len != cmp.len) return len < cmp.len;
        _FOR(i, len, 1)
            if(num[i] != cmp.num[i]) return num[i] < cmp.num[i];
        return false;
    }

    bool operator > (const BigInt &cmp) const { return cmp < *this; }
    bool operator <= (const BigInt &cmp) const { return !(cmp < *this); }
    bool operator != (const BigInt &cmp) const { return cmp < *this || *this < cmp; }
    bool operator == (const BigInt &cmp) const { return !(cmp < *this || *this < cmp); }

    BigInt operator + (const BigInt &A) const {
        BigInt S;
        S.len = max(len, A.len);
        FOR(i, 1, S.len){
            S.num[i] += num[i] + A.num[i];
            if(S.num[i] >= 10){
                S.num[i] -= 10;
                S.num[i + 1]++;
            }
        }
        while(S.num[S.len + 1]) S.len++;
        return S;
    }

    BigInt operator - (const BigInt &A) const {
        BigInt S;
        S.len = max(len, A.len);
        FOR(i, 1, S.len){
            S.num[i] += num[i] - A.num[i];
            if(S.num[i] < 0){
                S.num[i] += 10;
                S.num[i + 1]--;
            }
        }
        while(!S.num[S.len] && S.len > 1) S.len--;
        return S;
    }

    BigInt operator * (const BigInt &A) const {
        BigInt S;
        if((A.len == 1 && A.num[1] == 0) || (len == 1 && num[1] == 0)) return S;
        S.len = A.len + len - 1;
        FOR(i, 1, len)
            FOR(j, 1, A.len){
                S.num[i + j - 1] += num[i] * A.num[j];
                S.num[i + j] += S.num[i + j - 1] / 10;
                S.num[i + j - 1] %= 10;
            }
        while(S.num[S.len + 1]) S.len++;
        return S;
    }

    BigInt operator / (const BigInt &A) const {
        BigInt S;
        if((A.len == 1 && A.num[1] == 0) || (len == 1 && num[1] == 0)) return S;
        BigInt R, N;
        S.len = 0;
        _FOR(i, len, 1){
            N.itoBig(10);
            R = R * N;
            N.itoBig(num[i]);
            R = R + N;
            int flag = -1;
            FOR(j, 1, 10){
                N.itoBig(j);
                if(N * A > R){
                    flag = j - 1;
                    break;
                }
            }
            S.num[++S.len] = flag;
            N.itoBig(flag);
            R = R - N * A;
        }
        FOR(i, 1, S.len / 2) swap(S.num[i], S.num[len - i + 1]);
        while(!S.num[S.len] && S.len > 1) S.len--;
        return S;
    }

    BigInt operator % (const BigInt &A) const {
        BigInt S;
        BigInt P = *this / A;
        S = *this - P * A;
        return S;
    }
};