首页 > 其他分享 >ACM基础数论笔记

ACM基础数论笔记

时间：2024-02-04 10:57:50浏览次数：22  
标签：return space 数论 ll 笔记 int ACM equiv mod

基础数论部分

整除

定义

设\(a,b\in Z,a\neq0,若\exist q \in Z 使得b=aq\)，则b可被a整除，记作\(a\mid b\)，称b是a的倍数，a是b的约数

不能整除 \(a\nmid b\)

定理

  1. \(a\mid{b}\iff -a\mid{b} \iff a\mid{-b}\iff |a|\mid|b|\)
  2. \(a\mid b且b\mid c\Rightarrow a\mid c\)
  3. \(a\mid b 且 a\mid c \iff 对\forall x,y\in Z,有a\mid {bx+cy}\)
  4. \(m\neq 0 ,a\mid b \iff ma\mid mb\)
  5. \(a\mid b 且 b\mid a \Rarr b=\pm a\)
  6. \(b\neq 0,a\mid b \Rarr|a|\le|b|\)

约数

对于一个数n，其约数定义为能够整除n的数，在整数域内等价于因数

试除法求n的所有约数:

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

最大公约数(GCD)

指两个或多个整数中共有的约数中最大的一个\(a,b\)的最大公约数记为\((a,b)\)或\(\gcd(a,b)\)

特别的\(\gcd(0,a)=a\)

最常见使用辗转相除法求gcd

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

最小公倍数(LCM)

两个或多个整数最小的公共倍数，\(a,b\)的LCM记为\([a,b]\)

公式：\([a,b]=a/(a,b)*b\)

ll lcm(ll m,ll n){
    ll g1,b;
    g1 = __gcd(m,n);
    b = (m*n) / g1; 
    return b;
}

质数

一个正数p除了\(\pm 1,\pm p\)之外无其他约数，则称p为质数

若a是一个合数，则必有质数p，\(p\mid a\)

质数的个数是无穷的

判定质数的方法

试除法判质数

适用于数据范围\(\le10^{12}\)

试除法的原理就是用\([2,\sqrt{n}]\)内的所有数试着除n，如果都不能整除，就是素数

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

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

//常数优化 sqrt(x)/3
bool isPrime(int n) {
    if (n == 1) return false;
    if (n == 2 || n == 3) return true;
    if (n % 6 != 1 && n % 6 != 5) return false;
    for (int i = 5, j = n / i; i <= j; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) {
            return false;
        }
    }
    return true;
}

Miller Rabin素性测试

适用于数据范围\(>10^{12}\)时使用

费马素性测试：基于费马小定理

找一个数x，判定\(a^{m-1}mod\space m\equiv 1\),如果找到\(n\)个数满足判定，就把m认为是质数

正是由于费马小定理无法判断伪质数也叫Carmichael数，所以费马素性测试并不能保证完全正确

二次探测定理：如果\(p\)是一个奇素数，且\(e\ge 1\),则方程\(x^2\equiv1(mod\space p^e)\)仅有两个解：\(x=1和x=-1\)，\(e=1\)时方程仅有两个解\(x=1和x=p-1\)，称其为平凡平方根

Miller Rabin算法在费马素性测试基础上通过二次探测定理改进而来

如果一个数满足方程\(x^2\equiv1(mod\space n)\)但\(x\)不等于平凡平方根1或n-1，则称其为非平凡平方根，如果对模n存在1的非平凡平方根，n就是合数

ll mul(ll a, ll b, ll m) {
    return static_cast<__int128_t>(a) * b % m;
}
ll power(ll a, ll b, ll m) {
    ll res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(ll n) {
    if (n < 2)
        return false;
    static constexpr int A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    int s = __builtin_ctzll(n - 1);
    ll d = (n - 1) >> s;
    for (auto a : A) {
        if (a == n)
            return true;
        ll x = power(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool ok = false;
        for (int i = 0; i < s - 1; ++i) {
            x = mul(x, x, n);
            if (x == n - 1) {
                ok = true;
                break;
            }
        }
        if (!ok)
            return false;
    }
    return true;
}

标准分解形式

\(n=p_1^{k_1}p_2^{k_2}...p_n^{k_n}\) \(\{p_1<p_2<...<p_n\}\)

\(p_i\)为质数，也为质因数分解形式

算数基本定理：任意一个大于1的整数都可以被分解成若干个质数相乘的形式

  1. 设\(n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}\)

    \(m=p_1^{b_1}p_2^{b_2}...p_n^{b_n}\)

    若\(0\le b_i\le a_i,i=1,...,k\)，则m是n的正因数

  2. 设\(n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}，a_i>0,i=1,2,...,k\)，则n的正因数个数有\((a_1+1)(a_2+1)...(a_k+1)\)个

  3. 设\(n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}\)

    \(m=p_1^{b_1}p_2^{b_2}...p_n^{b_n}\)

    则\((a,b)=p_1^{\gamma_1}p_2^{\gamma_2}...p_n^{\gamma_n}\)

    \([a,b]=p_1^{\sigma_1}p_2^{\sigma_2}...p_n^{\sigma_n}\)

    其中 \(\gamma_i=min(a_i,b_i),\sigma_i=max(a_i,b_i),i=1,2,...,k\)

  4. 约数之和：\((p_1^0+p_1^1+...+p_1^{k_1})*(p_2^0+p_2^1+...+p_2^{k_2})*...*(p_n^0+...+p_k^{k_n})\)

质因数分解

试除法分解质因数

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

map<int,int> cnt;
void divide(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            while(x%i==0){
                x/=i;
                cnt[i]++;
            }
        }
    }
    if(x>1) cnt[x]++;
}

Pollard Rho算法

pollard rho用于求解大数质因子问题，使用Miller Rabin判断质数，原理是生日悖论，了解即可

ll mul(ll a, ll b, ll m) {
    return static_cast<__int128_t>(a) * b % m;
}
ll power(ll a, ll b, ll m) {
    ll res = 1 % m;
    for (; b; b >>= 1, a = mul(a, a, m))
        if (b & 1)
            res = mul(res, a, m);
    return res;
}
bool isprime(ll n) {//Miller Rabin部分
    if (n < 2)
        return false;
    static constexpr int A[] = {2, 3, 5, 7, 11, 13, 17, 19, 23};
    int s = __builtin_ctzll(n - 1);
    ll d = (n - 1) >> s;
    for (auto a : A) {
        if (a == n)
            return true;
        ll x = power(a, d, n);
        if (x == 1 || x == n - 1)
            continue;
        bool ok = false;
        for (int i = 0; i < s - 1; ++i) {
            x = mul(x, x, n);
            if (x == n - 1) {
                ok = true;
                break;
            }
        }
        if (!ok)
            return false;
    }
    return true;
}
std::vector<ll> factorize(ll n) {//pollard rho部分，所有的质因数都会作为vector元素返回
    std::vector<ll> p;
    std::function<void(ll)> f = [&](ll n) {
        if (n <= 10000) {
            for (int i = 2; i * i <= n; ++i)
                for (; n % i == 0; n /= i)
                    p.push_back(i);
            if (n > 1)
                p.push_back(n);
            return;
        }
        if (isprime(n)) {
            p.push_back(n);
            return;
        }
        auto g = [&](ll x) {
            return (mul(x, x, n) + 1) % n;
        };
        ll x0 = 2;
        while (true) {
            ll x = x0;
            ll y = x0;
            ll d = 1;
            ll power = 1, lam = 0;
            ll v = 1;
            while (d == 1) {
                y = g(y);
                ++lam;
                v = mul(v, std::abs(x - y), n);
                if (lam % 127 == 0) {
                    d = std::__gcd(v, n);
                    v = 1;
                }
                if (power == lam) {
                    x = y;
                    power *= 2;
                    lam = 0;
                    d = std::__gcd(v, n);
                    v = 1;
                }
            }
            if (d != n) {
                f(d);
                f(n / d);
                return;
            }
            ++x0;
        }
    };
    f(n);
    std::sort(p.begin(), p.end());
    return p;
}

整除函数

定义

设\(x\in R\),定义[x]等于不超过x的最大整数，称[x]为取整函数或高斯函数，也称[x]为x的整数部分，{x}为x的小数部分

性质

  1. \(x=[x]+{x}\)

  2. \([x]\le x <[x]+1,x-1<[x]\le x,0\le{\{x\}}<1\)

  3. 设\(n\in Z,则[n+x]=n+[x]\)

  4. \([x]+[y]\le{[x+y]},\{x\}+\{y\}\ge\{x+y\}\)

  5. 带余除法：设\(a,b\in Z,b>0,则a=b[\frac{a}{b}]+b\{\frac{a}{b}\},0\le b\{\frac{a}{b}\}\le b-1\)

  6. 若\(a,b\in Z_+,则b的倍数中小于等于a的正整数个数为[\frac{a}{b}]\)

  7. \(若x\le y,则 [x]\le [y]\)

二元一次不定方程

定义

未知数必须受到某种限制(如整数，正整数，有理数等)的方程，称为不定方程

设$a,b,c\in Z,ab\neq 0,称式子 ax+by=c $为关于变量x，y的二元一次不定方程

定理

  1. 设二元一次不定方程\(ax+by=c(a,b,c\in Z,ab\neq 0)\)

    有一整数解\(x=x_0,y=y_0,且(a,b)=d,a=a_1d,b=b_1d\)则此不定方程的一切整数解可以表示为\(x=x_0-b_1t,y=y_0-a_1t,t\in Z\)

  2. 二元一次不定方程\(ax+by=c\)有整数解的充要条件是\((a,b)\mid c\)

  3. 裴蜀定理：二元一次不定方程\(ax+by=c\)一定存在x,y 使得\(ax+by=(a,b)\)

    可以拓展到多元一次不定方程：

    void solve(){
    int n;
    cin>>n;
    vector<int> a(n);
    in(a,n);//输入n个系数
    int sum=0;
    For(i,0,a.size()){
        sum=__gcd(sum,abs(a[i]));//gcd(0,a)=a
    }
    cout<<sum<<"\n";
}

扩展欧几里得(exGCD)

求解二元一次不定方程\(ax+by=(a,b)\)的一个特解

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

如何用扩展欧几里得算法求二元一次不定方程\(ax+by=c,gcd(a,b)\mid c\)的解

先用exgcd求出\(ax+by=(a,b)\)的一个特解\(x_0,y_0\)，然后然后给每个数乘上\(c/gcd(a,b)\)即可

通解便是\(x=x_0+\frac{b}{\gcd(a,b)}*k,y=y_0-\frac{a}{\gcd(a,b)}*k\)

使用扩展欧几里得求线性同余方程：设同余方程\(ax\equiv b(mod\space c)\)

根据同余定义，我们可以将同余方程化为二元一次不定方程\(ax-cy= b\)，这个时候就可以使用exgcd求出一组\((a,c)\)的特解了，再乘以\(b/\gcd(a,c)\)就是最后的答案\(ans\)，如果结果要求是正数，我们可以使用\((ans+\frac{c}{gcd(a,c)})\%\frac{c}{gcd(a,c)}\)的形式获得最小正解，解题时要使b为正数

eg：[P1516 青蛙的约会 - 洛谷](P1516 青蛙的约会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn))

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
void solve(){
    int a,b,m,n,l;
    cin>>a>>b>>m>>n>>l;
    if(n-m<0)swap(a,b),swap(m,n);
    int x,y;
    int g=exgcd((n-m),l,x,y);
    if((a-b)%g){//如果最大公约数不是(a-b)的倍数一定无解
        cout<<"Impossible\n";
    }else{
        cout<<((x*((a-b)/g))%(l/g)+(l/g))%(l/g)<<"\n";//最小正整数解
    }
}

同余

定义

设\(m>0\)，如果\(a,b\)的差\(a-b\)能被m整除，即有q使得\(a-b=qm\) ，称a，b关于模m同余，记为\(a\equiv{b(mod\space m)}\)

\(eg:62\equiv{48(mod\space 7)}\)

性质

  1. 同余具有自反，对称，传递性,同余是等价关系

  2. 若\(a\equiv {b(mod \space m)},c\equiv{d(mod\space m)},则 a\pm{c}\equiv{b\pm{d}(mod\space m)}\)

  3. 若\(a\equiv {b(mod \space m)},c\equiv{d(mod\space m)},则 ac\equiv{bd(mod\space m)}\)，反之不然

  4. 若\(a\equiv {b(mod \space m)},且n\in N,则 a^n\equiv{b^n(mod\space m)}\)

  5. 若\(ac\equiv{bc(mod\space m)},且c\neq 0,则a\equiv{b(mod\space{\frac{m}{(c,m)}})}\)

  6. 若\(a\equiv b(mod\space m),m=qn,则a\equiv b(mod\space n)\)

  7. 若\(a\equiv b(mod\space m_i),i=1,2,3,...,n,则a\equiv b(mod\space [m_1,m_2,...m_n])\)

完全剩余系

如果a，b关于m同余，则a与b属于同一类，否则不属于同一类

这样可以得到m个类，即\(M_i=\{i+km|k\in Z\},i=0,1,2,...,m-1\)，称为模m的剩余类

从每个剩余数中各取一个数作为代表，这样得到的m个数成为模m的一个完全剩余系，也叫完系，比如\(\{1,2,...,m\}\)

当m为奇数时，\(\{0,\pm 1,\pm 2,...,\pm \frac{m-1}{2}\}\)是一个完系

当m为偶数时，\(\{0,\pm 1,\pm 2,...,\pm \frac{m}{2}\}\)是一个完系

当\(a_1,a_2,...a_m\)中每两个数互不同余，则它们毕分属于模m的m个剩余类，组成一个完系

如果\((n,m)=1\)，那么当\(a_1,a_2,...a_m\)是模m的完系时，\(na_1+k,na_2+k,...,na_m+k\)模m互不同余，因此他们也是模m的完系

缩系/既约剩余系

在完全剩余系中，与m互质的元素组成的子集

中国剩余定理(CRT)

求解同余方程的一个解，要求\(m_1,m_2,...m_n\)必须互质，如果不互质就需要使用扩展中国剩余定理exCRT

\(\begin{aligned}\left\{\begin{array}{lr}x\equiv{a_1(mod\space m_1)}\\x\equiv a_2(mod\space m_2)\\......\\x\equiv{a_n(mod\space m_n)}\end{array}\right.\end{aligned}\)

x的解公式：\(x= a_1*M_1*M^{-1}_1+a_2*M_2*M^{-1}_2+...+a_n*M_n*M^{-1}_n\)

其中，\(M_i=\frac{\prod\limits_{k=1}^nm_k}{m_i}\)，\(M^{-1}_i=inv(M_i)\)

excrt板子：

using ll = long long;
const int N = 1e5+10;
ll Ai[N], Mi[N];
int n; 
constexpr int qpow(int n, int k, int p) {
    int r = 1;
    for (; k; k >>= 1, n = n * n % p)
        if (k & 1) r = r * n % p;
    return r;
}
constexpr ll mul(ll a, ll b, ll p) {
    ll res = a * b - ll(1.L * a * b / p) * p;
    res %= p;
    if (res < 0) {
        res += p;
    }
    return res;
}
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) { x = 1, y = 0; return a; }
    ll gcd = exgcd(b, a % b, x, y), tp = x;
    x = y, y = tp - a / b * y;
    return gcd;
}
ll excrt() {
    ll x, y, k;
    ll M = Mi[1], ans = Ai[1];
    for (int i = 2; i <= n; ++ i) {
        ll a = M, b = Mi[i], c = (Ai[i] - ans % b + b) % b;
        ll gcd = exgcd(a, b, x, y), bg = b / gcd;
        if (c % gcd != 0) return -1;
        x = mul(x, c / gcd, bg);
        ans += x * M;
        M *= bg;
        ans = (ans % M + M) % M;
    }
    return (ans % M + M) % M;
}

费马小定理

定义

多项式展开中 \((x+y)^p=x^p+\binom{p}{1}x^{p-1}y+\binom{p}{2}x^{p-2}y+...+y^p\)

其中\(\binom{p}{k}=\frac{p!}{k!(p-k)!}\)，当p为质数时，对于满足\(1\le k\le p-1\)的k，\(p\nmid k!(p-k)!\)

而\(p|k!(p-k)!\frac{p!}{k!(p-k)!}\),所以\(p|\binom{p}{k},k=1,2,...,p-1\)

从而有\((x+y)^p\equiv{x^p+y^p(mod\space p)}\)

令x=1，y=1,可得\(2^p\equiv{2(mod\space p)}\)，令x=2，y=1,可得\(3^p\equiv{3(mod\space p)}\)，......

因此对于所有\(a=1,2,...,p-1\),都有\(a^p\equiv a(mod \space p)\)

得到费马小定理：对于任意整数a和质数p，都有\(a^p\equiv a(mod \space p)\)

若\(\gcd(a,p)=1,则a^{p-1}\equiv 1(mod \space p)\)

其逆定理不成立，即使得\(a^n\equiv{a(mod\space n)}\)成立的n不一定是质数，能使其成立的合数n称为伪质数

341最小伪质数，1000以下还有561和645是伪质数

威尔逊定理

若p为质数，则\((p-1)!\equiv{-1(mod \space p)}\)

逆元

\(aa'\equiv{1(mod\space p)}\)，\(a'\)称为a的逆元

所以从费马小定理可以得出，\(a'\equiv a^{p-2}(mod \space p)\)

逆元可以在模意义下用乘法代替原数除法进行运算，即\(a/b\equiv a*inv\space b(mod \space p)\)

费马小定理求逆元代码

const int mod = 1e9+7;
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int inv(int x){return qpow(x,mod-2);}

但是费马小定理求逆元也有局限性，就是p必须为一个质数，除了费马小定理，我们也可以使用扩展欧几里得求逆元，它要求a与模数p互质即可，p不必须为质数

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
int inv(int a, int p){
    int x, y;
    exgcd(a, p, x, y);
    return (p + x % p) % p;
}

欧拉定理

费马定理阐述的是在质数模下，指数的同余性质，当模是合数时，就要用欧拉定理

欧拉函数

\(\phi(n)\)：1到n中与n互质的数的个数

互质：\(\gcd(a,b)=1\)

\(eg:\phi(8)=4 \space \{1,3,5,7\}\)

求单个数字的欧拉函数：

int phi(int x){
    int res = x;
    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;
}

引理

  1. 若\(n\)为一个质数，则\(\phi(n)=n-1\)

  2. 若\(n\)为某一个素数p的幂次\(p^a\)，则\(\phi(p^a)=(p-1)*p^{a-1}\)

  3. 若\(n\)为两个质数\(a,b\)的积，则\(\phi(a*b)=\phi(a)*\phi(b)\)

  4. 设\(n=p_1^{k_1}p_2^{k_2}...p_n^{k_n}\) \(\{p_1<p_2<...<p_n\}\)，则\(\phi(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})\)

欧拉定理

设n为正整数，考虑\(mod\space n\)的缩系，对于缩系中的任意一个元素a，有\(a^{\phi(n)}\equiv{1(mod\space n)}\)

也就是说，若a与n互质，则\(a^{\phi(n)}\equiv{1(mod\space n)}\)

扩展欧拉定理

\(x^n\equiv\begin{aligned}\left\{\begin{array}{lr}x^n(mod\space m)&x<\phi(m)\\x^{n\space mod \space\phi(m)+\phi(m)}(mod\space \phi (m))&x\geq\phi(m)\end{array}\right.\end{aligned}\)

此时x与m可以不互质

标签：return,space,数论,ll,笔记,int,ACM,equiv,mod
From： https://www.cnblogs.com/KrowFeather/p/18005761

相关文章

  • 数位dp笔记
    数位dp学习笔记数位dp的问题题型一般是给定一个闭区间[L,R]，求这个区间中满足“某种条件”的数的个数的总数对于这类问题，我们首先统计[L,R]范围的满足条件的数字转化成统计[1,N]内满足条件的数字的数量那么ans[L,R]=ans[1,R]-ans[1,L-1];先将n转换成字符串str，使用记忆化搜索......
  • ACM常用模板
    usefulskill连续区间求和llsum(lll,llr){return(l+r)*(r-l+1)/2;}内置位运算__builtin_ffs(x)：返回x中最后一个为1的位是从后向前的第几位，如__builtin_ffs(0x789)=1,__builtin_ffs(0x78c)=3。于是，__builtin_ffs(x)-1就是x中最后一个为1的位的位置。__buil......
  • 数论基础（一）
    数学符号整除/同余理论常见符号整除符号：\(x\midy\)，表示\(x\)整除\(y\)。取模符号：\(x\bmody\)，表示\(x\)对\(y\)取模。互质符号：\(x\perpy\)，表示\(x\)与\(y\)互质。同余：\(n\equivk\pmodm\)，表示\(n\)与\(k\)在模\(m\)意义下同余。最大公约数：\(\gcd......
  • Pandas库学习笔记（4）---Pandas Panel
    PandasPanel  PandasPanel基本操作Panel数据3D容器.术语 Paneldata 源自计量经济学，名称来之于pandas− pan(el)-da(ta)-s.3个轴的名称描述如下-−items −轴0，每个items都对应一个包含在其中的DataFrame。major_axis −轴1，它是每个DataFrame的索引（行）。minor......
  • 《周期》霍华德马克思 读书笔记
    第七章投资人的心理和情绪钟摆周期像钟摆从最左端摆向平衡位置时他不会停下而会继续向右摆动，直到力量不再支持他向右继续摆动，调头返回投资人的心理在绝对乐观到绝对悲观之间摆动，绝对悲观时看到资产认为他像一个会带来成本的大楼，没有想到他能租出去带来收益。绝对乐观时认为资......
  • 图论算法学习笔记
    ybt1376floyd#include<iostream>#include<climits>#include<cstring>#include<queue>#include<vector>#defineinfinity0x3f3f3f3f#defineN105intn,m,G[N][N],dist[N][N];intmain(){ memset(dist,infinity,sizeof(dist)); st......
  • Docker笔记（一）docker 在linux里面的安装
    Docker笔记（一）docker在linux里面的安装为什么使用docker（docker理念）在开发环境，将源码+配置+软件等其他项目运行的所有的东西，都打包，直接都给运维，这样运维就不需要自己搭建项目运行的环境了，因为你已经拿到了开发人员本地的全部的东西，相当于拿到开发人员全部的东西，直接在运维那里就......
  • 【学习笔记】字符串
    1.KMP【模板】KMP朴素的比对是如下的：for(inti=0;i<a.size()-b.size();i++){ for(intj=0;j<b.size();j++){ if(a[i+j]!=b[j])break; if(j==b.size()-1)cout<<i<<''; }}设A串长度\(n\)，B串长度\(m\)，显然这么做是\(O(nm)\)的。很容易想到一个错误优化：如果失......
  • 数论
    数论1.快速幂解决次数很高的幂取模问题快速幂问题：求ab %p做法：（核心思想合并基数modp）利用while循环，循环条件是指数b不为0指数和1做&运算相当于将指数转为二进制再与1做&例如指数为6：就化成110&1为0每次&1会得到化成二进制后当前位数是1还是0还要设置一个基数base，每次base......
  • 【笔记】快速傅里叶变换
    快速傅里叶变换0记号\(\exp(x)=e^x\)。1复数(Complex)1.1三种形式代数形式：\(z=a+bi\)，其中\(a,b\in\mathbbR\)。三角形式：\(z=r(\cos\theta+i\sin\theta)\)，其中\(r=\sqrt{a^2+b^2}\)（\(a,b\)是在代数形式中定义的）。指数形式：\(z=r\cdote^{i\theta}\)。根据......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99