补充（自用）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

补充（自用）

作者：

Milonia , 2024-10-23 19:43:29 , 所有人可见 , 阅读 5

update:24/10/24

-2. 警钟敲响!!!!!!

不要用memset！宁可多写个for！

-1. 模版

// Author: Milonia     (O v O)

#include <iostream>
using namespace std;

#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
#define FOR(i,n) for(int i=1;i<=n;i++)
#define FOR_(i,n) for (int i=n;i>=1;i--)
#define FOR0(i,n) for (int i=0;i<=n;i++)
#define FOR0_(i,n) for (int i=n;i>=0;i--)
#define cdl cout<<'\n';
#define endl '\n'
#define lc p<<1
#define rc p<<1|1
#define F first
#define S second
#define pb push_back

string TT="-->";
template<typename T> void _p(const T& a) { cout<<a<<' '; }
template<typename T> void __p(const T& a) { cout<<a<<'_'; }
template<typename... T> void DE(T... a) { (_p(a), ...); cdl; }
template<typename... T> void CF(T... a) { (__p(a), ...); }
template<typename... T> void DE_(int num, T... a) { FOR(i,num) cout<<"*"; cout<<" "; (_p(a), ...); cdl; }
template<typename... T> void DE__(int num, T... a) { FOR(i,num) cout<<"_"; cout<<" "; (_p(a), ...); cdl; }



signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);



    return 0;
}

string TT="-->";
template<typename T> 
void _p(const T& a) { 
    cout<<a<<' ';
}

template<typename... T> 
void DE(T... a) { 
    (_p(a), ...); cdl;
}

template<typename... T> 
void DE_(int num, T... a) { 
    FOR(i,num) cout<<"*"; cout<<" "; 
    (_p(a), ...); cdl;
}

template<typename... T> 
void DE__(int num, T... a) { 
    FOR(i,num) cout<<"_"; cout<<" "; 
    (_p(a), ...); cdl; 
}

0. 加速

O3

#pragma GCC optimize(3,"Ofast","inline")

改成++ - -

把赋值成=1，改成++
赋值成=0，改成- -

火车头加速

#pragma GCC target('sse,sse2,sse3,sse4.1,sse4.2,popcnt,abm,mmx,avx')
#pragma comment(linker,'/STACK:102400000,102400000')
#pragma GCC optimize('Ofast')
#pragma GCC optimize('inline')
#pragma GCC optimize('-fgcse')
#pragma GCC optimize('-fgcse-lm')
#pragma GCC optimize('-fipa-sra')
#pragma GCC optimize('-ftree-pre')
#pragma GCC optimize('-ftree-vrp')
#pragma GCC optimize('-fpeephole2')
#pragma GCC optimize('-ffast-math')
#pragma GCC optimize('-fsched-spec')
#pragma GCC optimize('unroll-loops')
#pragma GCC optimize('-falign-jumps')
#pragma GCC optimize('-falign-loops')
#pragma GCC optimize('-falign-labels')
#pragma GCC optimize('-fdevirtualize')
#pragma GCC optimize('-fcaller-saves')
#pragma GCC optimize('-fcrossjumping')
#pragma GCC optimize('-fthread-jumps')
#pragma GCC optimize('-funroll-loops')
#pragma GCC optimize('-fwhole-program')
#pragma GCC optimize('-freorder-blocks')
#pragma GCC optimize('-fschedule-insns')
#pragma GCC optimize('inline-functions')
#pragma GCC optimize('-ftree-tail-merge')
#pragma GCC optimize('-fschedule-insns2')
#pragma GCC optimize('-fstrict-aliasing')
#pragma GCC optimize('-fstrict-overflow')
#pragma GCC optimize('-falign-functions')
#pragma GCC optimize('-fcse-skip-blocks')
#pragma GCC optimize('-fcse-follow-jumps')
#pragma GCC optimize('-fsched-interblock')
#pragma GCC optimize('-fpartial-inlining')
#pragma GCC optimize('no-stack-protector')
#pragma GCC optimize('-freorder-functions')
#pragma GCC optimize('-findirect-inlining')
#pragma GCC optimize('-fhoist-adjacent-loads')
#pragma GCC optimize('-frerun-cse-after-loop')
#pragma GCC optimize('inline-small-functions')
#pragma GCC optimize('-finline-small-functions')
#pragma GCC optimize('-ftree-switch-conversion')
#pragma GCC optimize('-foptimize-sibling-calls')
#pragma GCC optimize('-fexpensive-optimizations')
#pragma GCC optimize('-funsafe-loop-optimizations')
#pragma GCC optimize('inline-functions-called-once')
#pragma GCC optimize('-fdelete-null-pointer-checks')

1. 三分

求单峰函数极值

$O(logn)$

(若求单谷极值，就把 if 中的小于号，改成大于号即可)

//整数三分模板
while(l<r){
    int ml=(r+l)/2;
    int mr=ml+1;
    if(fx(ml)<fx(mr))l=ml+1;
    else r=mr-1;
}

//小数三分模板
while(l+eps<r) {
        double mid=(l+r)/2;
        double ml=mid;
        double mr=mid+eps;
        if(f(ml)<f(mr))l=ml+eps;
        else r=mr-eps;
}

例题： https://vjudge.net/problem/HDU-7467

2. 线段树

支持区间修改，区间查询

2.1 建树操作

$O(n)$

#define lc p<<1
#define rc p<<1|1
#define N 500005

int n,w[N];
struct node {
    int l,r,sum;
}tr[N*4];

void build(int p,int l,int r) {
    tr[p]={l,r, _w[l]_ };
    if (l==r) return;

    int mid=l+r>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    _tr[p].sum=tr[lc].sum+tr[rc].sum;_
    (其实就是 pushup 函数)
}

2.2 点修改

$O(logn)$

void update(int p,int x,int k) { // 在 x 的位置上增加 k 
    if (tr[p].l==x && tr[p].r==x) {
        _tr[p].sum+=k;_
        return;
    }

    int m=tr[p].l+tr[p].r>>1;
    if (x<=m) update(lc,x,k);
    if (x>m) update(rc,x,k);
    _tr[p].sum=tr[lc].sum+tr[rc].sum;_
}

2.3 区间查询

$O(logn)$

int query(int p,int x,int y) { // 区间查询 [x,y] 的和
    if (x<=tr[p].l && tr[p].r<=y) 
        return tr[p].sum;

    int mid=tr[p].l+tr[p].r>>1;
    int sum=0;
    if (x<=m) sum+=query(lc,x,y);
    if (m<y) sum+=query(rc,x,y);
    return sum;
}

2.4 区间修改 (懒标记)

$O(logn)$

void pushup(int p) {
    tr[p].sum=tr[lc].sum+tr[rc].sum;
}

void pushdown(int p) {
    if (tr[p].add) {
        tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);
        tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);
        tr[lc].add+=tr[p].add;
        tr[rc].add+=tr[p].add;
        tr[p].add=0;
    }
}

void update(int p,int x,int y,int k) {
    if (x<=tr[p].l && tr[p].r<=y) {
        tr[p].sum+=(tr[p].r-tr[p].l+1)*k;
        tr[p].add+=k;
        return;
    }

    int mid=tr[p].l+tr[p].r>>1;
    pushdown(p);
    if (x<=m) update(lc,x,y,k);
    if (m<y) update(rc,x,y,k);
    pushup(p);
}

3. 求树的直径

$O(m)$

const int N=1e5+5;
int d1[N], d2[N];
vector<int> E[N];
int d;

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}

signed main() {
    FOR(i,n-1) {
        int u, v; cin>>u>>v;
        E[u].push_back(v), E[v].push_back(u);
    }
    dfs(1,0);
    d+=1;
}

4. 二维凸包+旋转卡壳（求最长距离点对）

原题

在一个二维平面上，给定两个凸多边形 $A$ 和 $B$（可能有三个共线点）。$A$ 是固定的。你可以在平面内平移、旋转、翻转 $B$，但要确保 $A$ 和 $B$ 至少有一个点是重合的。求 $B$ 可以覆盖的点组成的图形的周长。

输入

第一行是一个正整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行包含一个正整数 $n$（$3≤n≤10^6$），表示凸多边形 $A$ 的顶点数量；
接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$,$y_i$ （$−10^8≤x_i,y_i≤10^8$），表示凸多边形 $A$ 的一个顶点 ($x_i, y_i$)；
下一行包含一个正整数 $m$（$3 \leq m \leq 10^6$），表示凸多边形 $B$ 的顶点数量；
接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x’_i, y’_i$（$-10^8 \leq x’_i, y’_i \leq 10^8$），表示凸多边形 $B$ 的一个顶点 ($x’_i, y’_i$)。

输出

对于每个测试用例，输出一行，包含一个实数，表示该测试用例的答案。答案的绝对或相对误差不超过 $10^{-9}$ 时才会被接受。

思路

答案即为 $2*pi*length+C$
$length$ 即为 $B$ 中的最长距离点对
$C$ 即为 $A$ 的周长

代码

$O(nlogn)$

// Author: Milonia     (O v O)

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define int_INF 0x3f3f3f3f
#define FOR(i,n) for(int i=1;i<=n;i++)
#define FOR_(i,n) for (int i=n;i>=1;i--)
#define FOR0(i,n) for (int i=0;i<=n;i++)
#define FOR0_(i,n) for (int i=n;i>=0;i--)
#define cdl cout<<endl;
#define lc p<<1
#define rc p<<1|1

const int MAXN = 1e6+5;
const long double pi=acos(-1);
struct Point{
    int x,y;
    Point(){}
    Point(int x, int y):x(x),y(y){}
    void input(){scanf("%lld%lld", &x, &y);}
    Point operator -(Point &b){return Point{x-b.x, y-b.y};}
    long double norm(){return (long double)1.0*x*x+(long double)1.0*y*y;}
    long double abs(){return (long double)__builtin_sqrt(norm()); }
}a[MAXN];
Point b[MAXN];  //凸包上的顶点
int N;           //点的总数
int bi = 0;    //凸包顶点的个数
int dis(const Point&p, const Point&q) {
    int dx = p.x - q.x, dy = p.y - q.y;
    return dx * dx + dy * dy;
}
int cross(const Point x, const Point y, const Point z) {
    //向量xy和向量xz之间的关系，若cross大于0，xz在xy的上方，若小于0，则xz在xy的下方
    return (x.x - y.x) * (x.y - z.y) - (x.y - y.y) * (x.x - z.x);
}
bool comp(const Point p, const Point q) {
    //比较两个点到目标点的角度，如果角度相同，让距离近的点排在前面
    int c = cross(a[0], p, q);
    if (c == 0) {
        return dis(a[0], p) - dis(a[0], q) < 0;
    }
    else {
        return c > 0;
    }
}
void findBag() {
    //寻找凸包
    //首先找到最左方、最下方的点
    for (int i = 1; i < N; i++) {
        if (a[i].x < a[0].x || (a[i].x == a[0].x && a[i].y < a[0].y)) {
            swap(a[i], a[0]);
        }
    }
    sort(a + 1, a + N, comp);
    b[0] = a[0];
    b[1] = a[1];
    bi = 2;
    for (int i = 2; i < N; i++) {
        while (bi > 1 && cross(b[bi - 2], b[bi - 1], a[i]) <= 0) {
            bi--;
        }
        b[bi++] = a[i];
    }
}

int t,n,m;
struct A{
    int x,y;
}a_[MAXN];
long double rotating_calipers(Point p[],int n){
    long double res = -1;
    for(int i = 0, k = 0;i < n;i ++){
        while((p[i]-p[k]).norm()<(p[i]-p[(k+1)%n]).norm()) k = (k+1)%n;
        res = max(res, (p[i]-p[k]).abs());
    }
    return res;
}
void sov() {
    scanf("%lld",&n);
    FOR(i,n) { // 读入 A 的边长
        int u,v; scanf("%lld %lld",&u,&v);
        a_[i]={u,v};
    }
    a_[n+1]=a_[1];

    scanf("%lld",&N);
    FOR0(i,N-1) { //注意下标从 0 到 N-1
        int u,v; scanf("%lld %lld",&u,&v);
        a[i]={u,v};
    }


    findBag();
//    cout<<endl;
//    for(int i=0;i<bi;i++) {
//        cout<<b[i].x<<" "<<b[i].y<<endl;
//    }
//    cout<<endl;
    long double ans=0;
    ans=rotating_calipers(b,bi);
//    cout<<ans<<endl;
    long double C=0;
    FOR(i,n) {
        auto op1=a_[i],op2=a_[i+1];
        C+=(long double)__builtin_sqrt((long double)1.0*(op1.x-op2.x)*(op1.x-op2.x)+(op1.y-op2.y)*(op1.y-op2.y));
    }

    printf("%.12Lf\n",(long double)2.0*pi*ans+C);
}

signed main(){

    scanf("%lld",&t);
    while (t--) sov();

    return 0;
}

模版

$O(nlogn)$

模版1-求凸包

const int MAXN = 1e6+5;
const long double pi=acos(-1);
struct Point{
    int x,y;
    Point(){}
    Point(int x, int y):x(x),y(y){}
    void input(){scanf("%lld%lld", &x, &y);}
    Point operator -(Point &b){return Point{x-b.x, y-b.y};}
    long double norm(){return (long double)1.0*x*x+(long double)1.0*y*y;}
    long double abs(){return (long double)__builtin_sqrt(norm()); }
}a[MAXN];
Point b[MAXN];  //凸包上的顶点
int N;           //点的总数
int bi = 0;    //凸包顶点的个数
int dis(const Point&p, const Point&q) {
    int dx = p.x - q.x, dy = p.y - q.y;
    return dx * dx + dy * dy;
}
int cross(const Point x, const Point y, const Point z) {
    //向量xy和向量xz之间的关系，若cross大于0，xz在xy的上方，若小于0，则xz在xy的下方
    return (x.x - y.x) * (x.y - z.y) - (x.y - y.y) * (x.x - z.x);
}
bool comp(const Point p, const Point q) {
    //比较两个点到目标点的角度，如果角度相同，让距离近的点排在前面
    int c = cross(a[0], p, q);
    if (c == 0) {
        return dis(a[0], p) - dis(a[0], q) < 0;
    }
    else {
        return c > 0;
    }
}
void findBag() {
    //寻找凸包
    //首先找到最左方、最下方的点
    for (int i = 1; i < N; i++) {
        if (a[i].x < a[0].x || (a[i].x == a[0].x && a[i].y < a[0].y)) {
            swap(a[i], a[0]);
        }
    }
    sort(a + 1, a + N, comp);
    b[0] = a[0];
    b[1] = a[1];
    bi = 2;
    for (int i = 2; i < N; i++) {
        while (bi > 1 && cross(b[bi - 2], b[bi - 1], a[i]) <= 0) {
            bi--;
        }
        b[bi++] = a[i];
    }
}

signed mian() {
    scanf("%lld",&N); // 读入点的个数
    FOR0(i,N-1) { // 读入点的坐标，注意下标是从 0 开始，到 N-1 
        int u,v; scanf("%lld %lld",&u,&v);
        a[i]={u,v};
    }

    findBag(); //调用函数即可
}

模版2-求答案

long double rotating_calipers(Point p[],int n){
    long double res = -1;
    for(int i = 0, k = 0;i < n;i ++){
        while((p[i]-p[k]).norm()<(p[i]-p[(k+1)%n]).norm()) k = (k+1)%n;
        res = max(res, (p[i]-p[k]).abs());
    }
    return res;
}
signed main() {
    findBag();
    long double ans=0; // ans 即为所求
    ans=rotating_calipers(b,bi);
}

调试部分-输出凸包中点的坐标

signed main() {
    for(int i=0;i<bi;i++) {
        cout<<b[i].x<<" "<<b[i].y<<endl;
    }
    cout<<endl;
}

5. 求最短距离点对

$O(nlogn)$

// Author: Milonia     (O v O)

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

const int maxn=1e6;
const double INF=1e50;//正无穷，可根据题意增大其值 
struct node{
    double x,y;
}point[maxn],term[maxn];
bool cmpx(node a,node b)//按x从小到大排序 
{
    return a.x<b.x;
}
bool cmpy(node a,node b)//按y从小到大排序 
{
    return a.y<b.y;
}
double distanc(node a,node b)//求两点之间距离 
{
    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}
double minpairsdis(int left,int right)//求当前集合最小点对之间的距离 
{
    double dis=INF;//初始化无穷大 
    if(left==right)//只有一个点返回无穷大 
        return dis;
    if(left+1==right)//有两个点，没得选，返回这两点之间距离 
        return distanc(point[left],point[right]);
    int mid=(left+right)/2;//分割集合的那条中线 
    double d1=minpairsdis(left,mid);//左边集合最小点对之间的距离 
    double d2=minpairsdis(mid+1,right);//右边集合最小点对之间的距离 
    dis=min(d1,d2);//最小距离 
    int i,j,k=0;
    for(i=left;i<=right;i++)//距离分割线小于等于dis之间的点 
    {
        if(fabs(point[i].x-point[mid].x)<=dis)
            term[k++]=point[i];
    }
    sort(term,term+k,cmpy);
    for(i=0;i<k;i++)
    {
        for(j=i+1;j<k;j++)
        {
            if(term[j].y-term[i].y>dis)//y值之差小于dis的才满足 
                break;
            else
                dis=min(dis,distanc(term[i],term[j]));
        }
    }
    return dis;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>point[i].x>>point[i].y;
    sort(point,point+n,cmpx);
    double ans=minpairsdis(0,n-1);
    cout<<ans<<endl; // ans 即为所求

    return 0;
}

6. 求欧拉函数

定义

欧拉函数（Euler’s totient function），即 $\varphi(n)$，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。
比如说 $\varphi(1) = 1$。
当 $n$ 是质数的时候，显然有 $\varphi(n) = n - 1$。

求一个数的欧拉函数

$O(\sqrt n)$

int euler_phi(int n) {
    int ans=n;
    for (int i=2;i*i<=n;i++)
        if (n%i==0) {
            ans=ans/i*(i-1);
            while (n%i==0) n/=i;
        }
    if (n>1) ans=ans/n*(n-1);
    return ans;
}

求 $n$ 个数的欧拉函数

$O(n)$

const int N = 1e6 + 5;
int p[N], t;        //质数及下标
int phi[N];         //欧拉函数
bool s[N];          //是否为合数

void get_euler(int n) {     //计算n以内的欧拉函数
    phi[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!s[i]) {
            p[++t] = i;
            phi[i] = i - 1;
        }
        for (int j = 1; p[j] <= n / i; j++) {
            s[i * p[j]] = true;
            if (i % p[j] == 0) {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
            phi[i * p[j]] = phi[i] * (p[j] - 1);
        }
    }
}

7. GCD - 最大公约数

辗转相除法（又称欧几里德算法）

$O(logn)$

int gcd(int a, int b){
    return b = 0 ? a : gcd(b, a % b);
}

更相减损术

$gcd(n,m)==gcd(n,n-m)$

Stein 算法（可看作更相减损术的应用）

$O(logn)$

$gcd(ka,kb)==k*gcd(a,b)$

int stein(int a, int b) {
    if (a < b)
        a ^= b, b ^= a, a ^= b;         // 交换，使a为较大数；
    if (b = 0)
        return a;                       // 当相减为零，即两数相等时，gcd=a；
    if ((!(a & 1)) & (!(b & 1)))
        return stein(a > 1, b > 1) < 1; // s1,注意最后的左移，在递归返回过程中将2因子乘上;
    else if ((a & 1) & (!(b & 1)))
        return stein(a, b > 1);         // s2;
    else if ((!(a & 1)) & (b & 1))
        return stein(a > 1, b);
    else
        return stein(a - b, b);         // s3;
}

多个数的 GCD

答案一定是每个数的约数，那么也一定是每相邻两个数的约数。
我们采用归纳法，可以证明，每次取出两个数求出答案后再放回去，不会对所需要的答案造成影响。

8. LCM - 最小公倍数

$O(logn)$

int lcm(int a,int b){
    return a / gcd(a,b) * b; // 先除后乘，以免溢出64位整数
}

9. 判断质数

试除法

$O(\sqrt n)$

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

Miller–Rabin

$O(k*logn)$

#include <ctime>

int qp(int base,int power,int MOD) {
    int res=1;
    while (power) {
        if (power&1) res=res*base%MOD;
        power>>=1;
        base=base*base%MOD;
    } 
    return res;
}

bool millerRabin(int n) {
    if (n < 3 || n % 2 == 0) return n == 2;
    if (n % 3 == 0) return n == 3;
    int u = n - 1, t = 0;
    while (u % 2 == 0) u /= 2, ++t;

    // int test_time=10;
    // test_time 为测试次数，建议设为不小于 8 的整数以保证正确率，但也不宜过大，否则会影响效率

    for (int i = 0; i < test_time; ++i) {
        // 0, 1, n-1 可以直接通过测试, a 取值范围 [2, n-2]
        int a = rand() % (n - 3) + 2, v = qp(a, u, n);
        if (v == 1) continue;
        int s;
        for (s = 0; s < t; ++s) {
            if (v == n - 1) break;    // 得到平凡平方根 n-1，通过此轮测试
            v = (long long)v * v % n;
        }
        // 如果找到了非平凡平方根，则会由于无法提前 break; 而运行到 s == t
        // 如果 Fermat 素性测试无法通过，则一直运行到 s == t 前 v 都不会等于 -1
        if (s == t) return 0;
    }
    return 1;
}

signed main() {
    srand(time(NULL));

    cout << millerRabin(50) << endl;

    return 0;
}

10. 格雷码

$0001(2)==1(10)$
$0011(2)==2(10)$
$0010(2)==3(10)$
$\dots$

转变方法

从左边第二位起，将每位与左边一位解码后的值异或，作为该位解码后的值（最左边一位依然不变）。依次异或，直到最低位。依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。

// 格雷码string -> 十进制
int str_gelei(string _str,int str_sz) { 
    int res=0,lt=0;
    for (int i=0;i<str_sz;i++) {
        res=(res<<1)+((_str[i]-'0')^lt);
        lt=((_str[i]-'0')^lt);
    }
    return res;
}

// 格雷码十进制 -> 十进制
int rev_g(int g) {
    int n = 0;
    for (; g; g >>= 1) n ^= g;
    return n;
}

11. 李超线段树

用来维护平面直角坐标系内，线段关系的树
支持动态插入线段
询问从某一个位置 $x$ 向下看，能看到的最高的线段（给一条竖线，问这条竖线与所有线段的最高节点）

预处理

// 所有 int/double 可根据情况选择

struct Line{
    int/double k,b; // 斜率 截距
}p[N*2];
int tr[N*4]; // 线段编号

int/double Y(int id,int x) { return p[id].k*x+p[id].b; } // 求Y值

插入线段

$O(nlog^2n)$

void change(int p,int l,int r,int L,int R,int id) { // 传入节点编号 当前区间范围 新线段的左右x的范围 插入的线段的编号
    int mid=l+r>>1;
    if (L<=l && r<=R) {
        if (Y(id,mid)>Y(tr[p],mid)) swap(id,tr[p]);
        if (Y(id,l)>Y(tr[p],l)) change(lc,l,mid,L,R,id);
        if (Y(id,r)>Y(tr[p],r)) change(rc,mid+1,r,L,R,id);
        return;
    }

    if (L<=mid) change(lc,l,mid,L,R,id);
    if (mid<R) change(rc,mid+1,r,L,R,id);
}

查询

直线 $O(logn)$
线段 $O(lognlogn)$

int/double query(int p,int l,int r,int x) {
    if (l==r) return Y(tr[p],x);

    int mid=l+r>>1;
    int/double t=Y(tr[p],x);
    if (x<=mid) return max(t,query(lc,l,mid,x));
    else return max(t,query(rc,mid+1,r,x));
}

例题

P4097 【模板】李超线段树

// Author: Milonia     (O v O)

#include <iostream>
using namespace std;

#define int long long
#define int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
#define FOR(i,n) for(int i=1;i<=n;i++)
#define FOR_(i,n) for (int i=n;i>=1;i--)
#define FOR0(i,n) for (int i=0;i<=n;i++)
#define FOR0_(i,n) for (int i=n;i>=0;i--)
#define cdl cout<<'\n';
#define lc p<<1
#define rc p<<1|1

const int N=1e5+5;
const int MOD1=39989;
const int MOD2=1e9;
const double eps=1e-9;

struct Line{
    double k,b;
}p[N*2];
int tr[N*4];
int lastans=0,idx=0;

int cmp(double x,double y) {
    if (x-y>eps) return 1;
    if (y-x>eps) return -1;
    return 0;
}

double Y(int id,int x) { return p[id].k*x+p[id].b; }


// 41 42 43 的大于等于，是为了满足题中的 “若同一个x值有两条线都是最大的，取编号最大的线” 这一条要求
void change(int p,int l,int r,int L,int R,int id) { 
    int mid=l+r>>1;
    if (L<=l && r<=R) {
        if (Y(id,mid)>=Y(tr[p],mid)) swap(id,tr[p]);
        if (Y(id,l)>=Y(tr[p],l)) change(lc,l,mid,L,R,id);
        if (Y(id,r)>=Y(tr[p],r)) change(rc,mid+1,r,L,R,id);
        return;
    }

    if (L<=mid) change(lc,l,mid,L,R,id);
    if (mid<R) change(rc,mid+1,r,L,R,id);
}

pair<double,int> pr_max(pair<double,int> op1,pair<double,int> op2) {
    if (cmp(op1.first,op2.first)==1) return op1;
    else if (cmp(op1.first,op2.first)==-1) return op2;
    else return op1.second<op2.second?op1:op2;
}

pair<double,int> query(int p,int l,int r,int x) {
    // cout<<Y(tr[p],x)<<' '<<tr[p]<<endl;
    if (r<x || x<l) return {0,0};
    if (l==r) return {Y(tr[p],x),tr[p]};

    int mid=l+r>>1;
    pair<double,int> t={Y(tr[p],x),tr[p]};
    return pr_max(pr_max(t,query(lc,l,mid,x)),query(rc,mid+1,r,x));
}

void add(int x0,int x1,int y0,int y1) {
    if (x0!=x1) {
        p[++idx].k=1.0*(y1-y0)/(x1-x0);
        p[idx].b=1.0*y0-p[idx].k*x0;
    } else {
        p[++idx].k=0;
        p[idx].b=max(y0,y1);
    }
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n; cin>>n;
    FOR(i,n) {
        // cout<<i<<' '<<lastans<<endl;
        int op; cin>>op;
        if (op) {
            int x0,x1,y0,y1; cin>>x0>>y0>>x1>>y1;
            x0=(x0+lastans-1+MOD1)%MOD1+1;
            x1=(x1+lastans-1+MOD1)%MOD1+1;
            y0=(y0+lastans-1+MOD2)%MOD2+1;
            y1=(y1+lastans-1+MOD2)%MOD2+1;


            if (x0>x1) swap(x0,x1),swap(y0,y1);

            add(x0,x1,y0,y1);
            change(1,1,MOD1,x0,x1,idx);
            // cout<<x0<<' '<<y0<<' '<<x1<<' '<<y1<<'-'<<idx<<endl;
        } else {
            int x; cin>>x;
            x=(x+lastans-1+MOD1)%MOD1+1;

            lastans=query(1,1,MOD1,x).second;

            // cout<<query(1,1,MOD1,x).first<<"__"<<endl;
            cout<<lastans<<endl;
        }
    }

    return 0;
}
/*
hack1:

=>
3
1 2 1 1 1
1 1 2 2 1
0 2

<=
1
*/

12. int128

__int128： $-2^{127}~\sim~2^{127}-1$

可以存 long long 的平方，实测范围达到了 $9*10^{37}$
记得不要写 IOS

快读

inline __int128 read() {
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

输出

inline void write(__int128 x) {
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

13. 组合数

13.1 组合数1

求 $n$ 组 $C^{b}_{a}$ ，$b\leq a\leq 2000$ ，$n\leq 10^5$

定理：$C^{b}_{a}=C^{b-1}_{a-1}+C^{b}_{a-1}$

#include <iostream>
using namespace std;

const int N=2010,MOD=1e9+7;
int c[N][N];

void init() {
    for (int i=0;i<N;i++)
        for (int j=0;j<=i;j++) 
            if (!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
}

int main(){
    init();
    int t,a,b; cin>>t;
    while (t--) {
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
}

13.2 组合数2

求 $n$ 组 $C^{b}_{a}$ ，$b\leq a\leq 10^5$ ，$n\leq 10000$

定理：$C^{b}_{a}=\frac{a!}{b!*(a-b)!}$

#include <iostream>
using namespace std;

#define int long long

const int N=1e5+5,MOD=1e9+7;
int fact[N],infact[N];

int qp(int base,int power,int p) {
    int res=1;
    while (power) {
        if (power&1) res=res*base%MOD;
        power>>=1;
        base=base*base%MOD;
    }
    return res;
}

signed main() {
    fact[0]=infact[0]=1;
    for (int i=1;i<N;i++) {
        fact[i]=fact[i-1]*i%MOD;
        infact[i]=infact[i-1]*qp(i,MOD-2,MOD)%MOD;
    }

    // 另外一个方法求 infact
    infact[N]=qp(f1[N],MOD-2,MOD);
    for (int i=N-1;i>=0;i--)
        infact[i]=infact[i+1]*(i+1)%MOD;


    int t; cin>>t;
    while (t--) {
        int a,b;
        cin>>a>>b;
        cout<<fact[a]*infact[b]%MOD*infact[a-b]%MOD<<endl;
    }
}

13.3 组合数3

求 $n$ 组 $C^{b}_{a}$ ，$b\leq a\leq 10^{18}$ ，$n\leq 20$

定理：$C^{b}_{a}=C^{b\space mod\space p}_{a\space mod\space p}*C^{b\space /\space p}_{a\space /\space p}$

#include <iostream>
using namespace std;

#define int long long

int p;

int qp(int base,int power,int p) {
    int res=1;
    while (power) {
        if (power&1) res=res*base%p;
        power>>=1;
        base=base*base%p;
    }
    return res;
}

int C(int a,int b) {
    int res=1;
    for (int i=1,j=a;i<=b;i++,j--) {
        res=res*j%p;
        res=res*qp(i,p-2,p)%p;
    }
    return res;
}

int lucas(int a,int b) {
    if (a<p && b<p) return C(a,b);
    else return C(a%p,b%p)*lucas(a/p,b/p)%p;
}

signed main() {
    int t; cin>>t;
    while (t--) {
        int a,b; cin>>a>>b>>p;
        cout<<lucas(a,b)<<endl;
    }
}

14. 位运算小寄巧

14.1 AND （&）

x & y = y & x
x & (y & z) = (x & y) & z
x & 0xFFFF = x –> 0xFFFF 是所有位都是 1
x & 0 = 0
x & x = x

14.2 OR （|）

x | y = y | x
x | (y | z) = (x | y) | z
x | 0 = x
x | 0xFFFF = 0xFFFF
x | x = x

14.3 NOT （~）

~(~x) = x

14.4 XOR （^）

x ^ y = y ^ x
x ^ (y ^ z) = (x ^ y) ^ z
x ^ 0 = x
x ^ y ^ y = x
x ^ x = 0
x ^ 0xFFFF = ~x

此外, XOR 可以用其他三种基础位运算表示 (AND, OR, NOT)
- a ^ b = (a | b) & (~a | ~b)
- a ^ b = (a & ~b) | (~a & b)

14.5 Others

x | (x & y) = x
x & (x | y) = x
~(x | y) = ~x & ~y
~(x & y) = ~x | ~y
x | (y & z) = (x | y) & (x | z)
x & (y | z) = (x & y) | (x & z)
x & (y ^ z) = (x & y) ^ (x & z)
x + y = (x ^ y) + ((x & y) << 1)
x - y = ~(~x + y)
a + b = (a & b) + (a | b)
a + b = (a ^ b) + 2 * (a & b)
a | b = (a & b) + (a ^ b)

15. 中国剩余定理（CRT）

$O(nlogc)$

作用

![[Pasted image 20240911225229.png]]

Latex 实在没写出来

步骤

![[Pasted image 20240911225259.png]]

板子 - LL

int exgcd(int a,int b,int &x,int &y) {
    if (b==0) {
        x=1,y=0;
        return a;
    }
    int d,x1,y1;
    d=exgcd(b,a%b,x1,y1);
    x=y1,y=x1-a/b*y1;
    return d;
}

int CRT(int m[],int r[]) { // m 为模数的数组   r 为余数的数组
    int M=1,ans=0;
    for (int i=1;i<=n;i++) M*=m[i];
    for (int i=1;i<=n;i++) {
        int c=M/m[i],x,y;
        exgcd(c,m[i],x,y);
        ans=(ans+r[i]*c*x%M)%M;
    }
    return (ans%M+M)%M;
}

板子 - int128

但其实没用，上面那个改成 int128 即可

//问题：求解同余方程组
// x ≡ a1 (mod b1)
// x ≡ a2 (mod b2)
// x ≡ a3 (mod b3)
//  ······
// x ≡ an (mod bn)
//其中b1，b2，b3，······ bn 为不一定两两互质的整数，求x的最小非负整数

//模板
#include<bits/stdc++.h>
#define up(i, x, y) for(__int128 i = x; i <= y; i++)
#define down(i, x, y) for(__int128 i = x; i >= y; i--)
#define maxn ((int)1000 + 10)
#define INF 0x3f3f3f3f
using namespace std;


__int128 n, ai[maxn], bi[maxn];// bi存余数

__int128 exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y)
{
    if(!b){ x = 1; y = 0; return a;}
    __int128 gcd = exgcd(b, a % b, x, y);
    __int128 t = x; x = y;
    y = t - a / b * y;
    return gcd;
}

__int128 crt()
{
    __int128 x, y, k;
    __int128 M = bi[1], ans = ai[1];//第一个方程的解特判
    for(__int128 i = 2; i <= n; i++)
    {
        __int128 a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;//ax≡c(mod b)
        __int128 gcd = exgcd(a, b, x, y), bg = b / gcd;
        if(c % gcd != 0) return -1;//判断是否无解
        x = (x * (c / gcd) % bg);
        ans += x * M;//更新前k个方程组的答案
        M *= bg;//M为前k个m的lcm
        ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
}
__int128 f[maxn];

inline __int128 read()
{
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

inline void write(__int128 x)
{
    if(x<0)
    {
        putchar('-');
        x=-x;
    }
    if(x>9)
        write(x/10);
    putchar(x%10+'0');
}

int main()
{
    init();
    n = read();
    for(__int128 i = 1; i <= n; i++)
         bi[i] = read(),  ai[i] = read() ;
    __int128 ans = excrt();
    write(ans);
    return 0;
}

#define maxn ((int)1000 + 10)
__int128 n, ai[maxn], bi[maxn];// bi存余数 ai存模数

__int128 exgcd(__int128 a, __int128 b, __int128 &x, __int128 &y) {
    if(!b) { x = 1; y = 0; return a;}
    __int128 gcd = exgcd(b, a % b, x, y);
    __int128 t = x; x = y;
    y = t - a / b * y;
    return gcd;
}

__int128 crt() {
    __int128 x, y, k;
    __int128 M = bi[1], ans = ai[1];//第一个方程的解特判
    for(__int128 i = 2; i <= n; i++) {
        __int128 a = M, b = bi[i], c = (ai[i] - ans % b + b) % b;//ax≡c(mod b)
        __int128 gcd = exgcd(a, b, x, y), bg = b / gcd;
        if(c % gcd != 0) return -1;//判断是否无解
        x = (x * (c / gcd) % bg);
        ans += x * M;//更新前k个方程组的答案
        M *= bg;//M为前k个m的lcm
        ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
}

16. 扩展中国剩余定理（EXCRT）

![[Pasted image 20240911235450.png]]
![[Pasted image 20240911235503.png]]

模版

int exgcd(int a,int b,int &x,int &y) {
    if (b==0) {
        x=1,y=0;
        return a;
    }
    int d,x1,y1;
    d=exgcd(b,a%b,x1,y1);
    x=y1,y=x1-a/b*y1;
    return d;
}

int EXCRT(int m[],int r[]) {
    int m1=0,m2=0,r1=0,r2=0,p=0,q=0;
    m1=m[1],r1=r[1];
    for (int i=2;i<=n;i++) {
        m2=m[i],r2=r[i];
        int d=exgcd(m1,m2,p,q);
        if ((r2-r1)%d) return -1;
        p=p*(r2-r1)/d;
        p=(p%(m2/d)+m2/d)%(m2/d);
        r1=m1*p+r1;
        m1=m1*m2/d;
    }
    return (r1%m1+m1)%m1;
}

17. 组合数

17.1 组合数 1

求 $n$ 组 $C^{b}_{a}$ ， $b\leq a\leq 2000$ ， $n\leq 10^5$

定理： $C^{b}_{a}=C^{b-1}_{a-1}+C^{b}_{a-1}$

#include <iostream>
using namespace std;

const int N=2010,MOD=1e9+7;
int c[N][N];

void init() {
    for (int i=0;i<N;i++)
        for (int j=0;j<=i;j++) 
            if (!j) c[i][j]=1;
            else c[i][j]=(c[i-1][j]+c[i-1][j-1])%MOD;
}

int main(){
    init();
    int t,a,b; cin>>t;
    while (t--) {
        cin>>a>>b;
        cout<<c[a][b]<<endl;
    }
}

17.2 组合数 2

求 $n$ 组 $C^{b}_{a}$ ， $b\leq a\leq 10^5$ ， $n\leq 10000$

定理： $C^{b}_{a}=\frac{a!}{b!*(a-b)!}$

#include <iostream>
using namespace std;

#define int long long

const int N=1e5+5,MOD=1e9+7;
int fact[N],infact[N];

int qp(int base,int power,int p) {
    int res=1;
    while (power) {
        if (power&1) res=res*base%MOD;
        power>>=1;
        base=base*base%MOD;
    }
    return res;
}

signed main() {
    fact[0]=infact[0]=1;
    for (int i=1;i<N;i++) {
        fact[i]=fact[i-1]*i%MOD;
        infact[i]=infact[i-1]*qp(i,MOD-2,MOD)%MOD;
    }

    // 另外一个方法求 infact
    infact[N]=qp(f1[N],MOD-2,MOD);
    for (int i=N-1;i>=0;i--)
        infact[i]=infact[i+1]*(i+1)%MOD;


    int t; cin>>t;
    while (t--) {
        int a,b;
        cin>>a>>b;
        cout<<fact[a]*infact[b]%MOD*infact[a-b]%MOD<<endl;
    }
}

17.3 组合数 3

求 $n$ 组 $C^{b}_{a}$ ， $b\leq a\leq 10^{18}$ ， $n\leq 20$

定理： $C^{b}_{a}=C^{b\space mod\space p}_{a\space mod\space p}*C^{b\space /\space p}_{a\space /\space p}$

#include <iostream>
using namespace std;

#define int long long

int p;

int qp(int base,int power,int p) {
    int res=1;
    while (power) {
        if (power&1) res=res*base%p;
        power>>=1;
        base=base*base%p;
    }
    return res;
}

int C(int a,int b) {
    int res=1;
    for (int i=1,j=a;i<=b;i++,j--) {
        res=res*j%p;
        res=res*qp(i,p-2,p)%p;
    }
    return res;
}

int lucas(int a,int b) {
    if (a<p && b<p) return C(a,b);
    else return C(a%p,b%p)*lucas(a/p,b/p)%p;
}

signed main() {
    int t; cin>>t;
    while (t--) {
        int a,b; cin>>a>>b>>p;
        cout<<lucas(a,b)<<endl;
    }
}

18. 找质因数

18.1 求所有因数

$O(\sqrt n )$

vector<int> get_dividors(int n) {       //求n的所有因数，保存至res向量中
    vector<int> res;
    for (int i = 1; i <= n / i; i++)
        if (n % i == 0) {
            res.push_back(i);
            if (i != n / i)             //完全平方数，不能重复添加
                res.push_back(n / i);
        }
    sort(res.begin(), res.end());       //排序，时间复杂度小于sqrt(n)
    return res;
}

分解质因数

#include<iostream>
using namespace std;
int main() {
    int n, i = 2;
    cin >> n;
    while (n != 1) {
        int t = 0;
        while (n % i == 0) {    //满足这个条件的i一定是质数
            n /= i;
            t++;                //记录质因数i出现的次数
        }
        if (t == 1)
            printf("%d", i);
        if (t > 1)
            printf("%d^%d", i, t);
        if (t > 0 && n != 1)
            printf("*");
        i++;
    }
    return 0;
}

求因数个数

$O(\sqrt n )$

int cnt_dividors(int n) {
    int res = 1;
    int p = 2;                  //枚举每个数
    while (n != 1) {
        int a = 0;              //质因数个数
        while (n % p == 0) {    //成立时p一定为质数
            n /= p;
            a++;
        }
        res *= (a + 1);
        p++;
    }
    return res;
}

求因数之和

LL sum_dividors(int n) {
    LL res = 1;
    int p = 2;                  //枚举每个数
    while (n != 1) {
         LL t = 1;
        while (n % p == 0) {    //成立时p一定为质数
            n /= p;
            t = t * p + 1;
        }
        res *= t;
        p++;
    }
    return res;
}

19. 高精度

高级整合板子（无除法）

const int N=1000005;
struct bign {
    int len,s[N];
    bign() { memset(s,0,sizeof (s)); len=1; }
    bign(int num) { *this=num; }
    bign(char *num) { *this=num; }
    bign operator =(int num) {
        char c[N];
        sprintf(c,"%d",num);
        *this=c;
        return *this;
    }
    bign operator =(const char *num) {
        len=strlen(num);
        for (int i=0;i<len;i++) s[i]=num[len-1-i]-'0';
        return *this;
    }
    string str() {
        string res="";
        for (int i=0;i<len;i++) res=(char)(s[i]+'0')+res;
        return res;
    }
    void clean() {
        while (len>1 && !s[len-1]) len--;
    }
    bign operator +(const bign &b) {
        bign c;
        c.len=0;
        for (int i=0,g=0;g||i<len||i<b.len;i++) {
            int x=g;
            if (i<len) x+=s[i];
            if (i<b.len) x+=b.s[i];
            c.s[c.len++]=x%10;
            g=x/10;
        }
        return c;
    }
    bign operator -(const bign &b) {
        bign c;
        c.len=0;
        int x;
        for (int i=0,g=0;i<len;i++) {
            int x=s[i]-g;
            if (i<b.len) x-=b.s[i];
            if (x>=0) g=0;
            else {
                x+=10;
                g=1;
            }
            c.s[c.len++]=x;
        }
        c.clean();
        return c;
    }
    bign operator *(const bign &b) {
        bign c;
        c.len=len+b.len;
        for (int i=0;i<len;i++) for (int j=0;j<b.len;j++) c.s[i+j]+=s[i]*b.s[j];
        for (int i=0;i<c.len-1;i++) { c.s[i+1]+=c.s[i]/10; c.s[i]%=10; }
        c.clean();
        return c;
    }
    bool operator <(const bign &b) {
        if (len!=b.len) return len<b.len;
        for (int i=len-1;i>=0;i--)
            if (s[i]!=b.s[i]) return s[i]<b.s[i];
        return false;
    }
    bign operator +=(const bign &b) {
        *this=*this+b;
        return *this;
    }
    bign operator -=(const bign &b) {
        *this=*this-b;
        return *this;
    }
};
istream& operator >>(istream &in,bign &x)
{
    string s;
    in>>s;
    x=s.c_str();
    return in;
}
ostream& operator <<(ostream &out,bign &x)
{
    out<<x.str();
    return out;
}


signed main() {
    bign a,b,c;
    cin>>a>>b;

    c=a+b;

    if (a<b) {
        c=b-a;
        cout<<"-";
        cout<<c<<endl;
    } else {
        c=a-b;
        cout<<c<<endl;
    }

    c=a*b;

    cout<<c<<endl;
    return 0;
}

之前（都有）

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A,vector<int> &B){
    if (A.size()<B.size()) return add(B,A);

    vector<int> C;
    int t=0;
    for (int i=0;i<A.size();i++){
        t+=A[i];
        if (i<B.size()) t+=B[i];
        C.push_back(t%10);
        t/=10;
    }

    if (t) C.push_back(t);
    return C;
}

// 比较
bool cmp(vector<int> &A,vector<int> &B){
    if (A.size()!=B.size()) return A.size()>B.size();
    for (int i=A.size()-1;i>=0;i--) 
        if (A[i]!=B[i]) return A[i]>B[i];
    return true;
}

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A,vector<int> &B){
    vector<int> C;
    int t=0;
    for (int i=0;i<A.size();i++){
        t=A[i]-t;
        if (i<B.size()) t-=B[i];
        C.push_back((t+10)%10);
        if (t<0) t=1;
        else t=0;
    }

    while (C.size()>1 && C.back() ==0) C.pop_back() ;
    return C;
}

// C = A * b, A >= 0, b > 0
// 高精度*低精度
vector<int> mul(vector<int> &A,int b){
    vector<int> C;
    int t=0;
    for (int i=0;i<A.size() || t;i++) {
        if (i<A.size()) t+=A[i]*b;
        C.push_back(t%10);
        t/=10;
    }
    while (C.size()>1 && C.back()==0) C.pop_back();
    return C;
}

// O(nm)
// C = A * B, A >= 0, B >= 0
// 高精度*高精度
vector<int> mul(const vector<int> &A, const vector<int> &B) {
    vector<int> C(A.size() + B.size());
    for (int i = 0; i < A.size(); i++) {
        for (int j = 0; j < B.size(); j++) {
            C[i + j] += A[i] * B[j];
        }
    }
    int t = 0;
    for (int i = 0; i < C.size(); i++) {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}

// A / b = C ... r, A >= 0, b > 0
// 高精度/低精度
int rr; // 余数
vector<int> div(vector<int> &A,int b,int &r){
    vector<int> C;
    r=0;
    for (int i=A.size()-1;i>=0;i--){
        r=r*10+A[i];
        C.push_back(r/b);
        r%=b;
    }
    reverse(C.begin(),C.end());
    while (C.size()>1 && C.back()==0) C.pop_back();
    return C;
}

// O((n-m)*n)
// 高精度/高精度
pair<vector<int>, vector<int>> div(vector<int> A, const vector<int> &B) {
    vector<int> C, R;
    int n = A.size(), m = B.size(), d = n - m;
    C.resize(d + 1, 0);
    // 枚举补 0 的个数
    for (int len = d; len >= 0; len--) {
        vector<int> Bp(len, 0);
        for (int x : B) Bp.push_back(x);

        // A >= Bp
        while (!cmp(A, Bp)) {
            C[len] += 1;
            A = sub(A, Bp);
        }
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    R = A;
    return make_pair(C, R);
}


int main(){
    string a,b;
    vector<int> A,B;

    // 读入处理
    cin >> a >> b;
    for (int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');
    for (int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');

    // 使用 + 
    auto C=add(A,B);
    // 使用 - 
    if (cmp(A,B)){
        auto C=sub(A,B);
        for (int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    } else {
        auto C=sub(B,A);
        printf("-");
        for (int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    }
    // 使用 * 1
    auto C=mul(A,b);
    // 使用 / 1
    auto C=div(A,b,rr);

    // 输出
    for (int i=C.size()-1;i>=0;i--) printf("%d",C[i]);
    return 0;
}

0 评论

App 内打开

补充（自用）

-2. 警钟敲响!!!!!!

-1. 模版

0. 加速

O3

改成++ - -

火车头加速

1. 三分

2. 线段树

2.1 建树操作

2.2 点修改

2.3 区间查询

2.4 区间修改 (懒标记)

3. 求树的直径

4. 二维凸包+旋转卡壳（求最长距离点对）

原题

输入

输出

思路

代码

模版

模版1-求凸包

模版2-求答案

调试部分-输出凸包中点的坐标

5. 求最短距离点对

6. 求欧拉函数

定义

求一个数的欧拉函数

求 $n$ 个数的欧拉函数

7. GCD - 最大公约数

辗转相除法（又称欧几里德算法）

更相减损术

Stein 算法（可看作更相减损术的应用）

多个数的 GCD

8. LCM - 最小公倍数

9. 判断质数

试除法

Miller–Rabin

10. 格雷码

转变方法

11. 李超线段树

预处理

插入线段

查询

例题

12. int128

快读

输出

13. 组合数

13.1 组合数1

13.2 组合数2

13.3 组合数3

14. 位运算小寄巧

14.1 AND （&）

14.2 OR （|）

14.3 NOT （~）

14.4 XOR （^）

14.5 Others

15. 中国剩余定理 （CRT）

作用

步骤

板子 - LL

板子 - int128

16. 扩展中国剩余定理 （EXCRT）

模版

17. 组合数

17.1 组合数 1

17.2 组合数 2

17.3 组合数 3

18. 找质因数

18.1 求所有因数

分解质因数

求因数个数

求因数之和

19. 高精度

高级整合板子（无除法）

之前（都有）

0 评论

15. 中国剩余定理（CRT）

16. 扩展中国剩余定理（EXCRT）