基础数论学习总结 | Llf0703's blog

基础数论学习总结

Llf0703 5月 09, 2018

原本打算先学Splay的，但想到提高组一般不考，而且我其它东西还差的多，就先把基础数论的东西复习一下，并且加深一下难度，~~还做了n多道水题，虽然主要是之前没过的~~。

1.整除

这里就把整除的性质列一下：

如果$a \mid b$且$b \mid c$，那么$a \mid c$
$a \mid b$且$a \mid c$等价于$\forall x,y$，有$a \mid (b \times x + c \times y)$
设$m\neq 0$,那么$a \mid b $等价于$(m \times a) \mid (m \times b)$
设$x,y$满足$a \times x+b \times y=1$且$a \mid n,b \mid n$，那么$(a \times b) \mid n$
若$b=q \times d+c$,那么$d \mid b$的充要条件是$d \mid c$

2.同余

同余性质：

自反性 $a\equiv a(mod m) $
对称性若$a\equiv b(mod m)$则$b\equiv a(mod m)$
传递性若$a\equiv b(mod m),b\equiv c(mod m)$，则$a\equiv c(mod m)$
同加性若$a\equiv b(modm)$，则$a+c\equiv b+c(modm)$
同乘性(1) 若$a\equiv b(modm)$，则$a\times c\equiv b\times c(modm)$
同乘性(2) 若$a\equiv b(modm),c\equiv d(modm)$ ，则$a\times c\equiv b\times d(modm)$
同幂性若$a\equiv b(modm)$，则$a^{n}\equiv b^{n} (modm)$

3.最大公约数(gcd)

辗转相除法

基础方法，不再赘述

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

二进制算法

不断去除因数2来提高gcd的效率

inline int gcd(int x,int y)
{
    int i,j;
    if (x==0) return y;
    if (y==0) return x;
    for (i=0;0==(x&1);i++) x>>=1;//去掉2
    for (j=0;0==(y&1);j++) y>>=1;
    if (i>j) i=j;
    for (;;)
    {
        if (x<y) x^=y,y^=x,x^=y;
        if (0==(x-=y)) return y<<i;//如果x==y gcd==x==y
        while (0==(x&1)) x>>=1;
    }
}

扩展欧几里得算法

扩展欧几里得算法用来在已知$(a,b)$，求$(x,y)$，使$a\times x+b\times y=gcd(a,b)$

void exgcd(LL l,LL r,LL &x,LL &y)
{
    if (r==0) x=1,y=0;
    else
    {
        exgcd(r,l%r,y,x);
        y-=l/r*x;
    }
}

例题：洛谷P1516 青蛙的约会

#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n,m,a,b,c,x,y,l,X,Y;

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

inline LL exgcd(LL l,LL r,LL &X,LL &Y)
{
    if (r==0)
    {
        X=1; Y=0;
        return l;
    }
    LL a=exgcd(r,l%r,Y,X);
    Y-=l/r*X;
    return a;
}

int main()
{
    x=read(); y=read(); m=read(); n=read(); l=read();
    LL deltav=(m>=n) ? m-n : n-m;
    LL deltas=(m>=n) ? y-x : x-y;
    LL k=exgcd(deltav,l,X,Y);
    if (deltas%k!=0) printf("Impossible");
    else printf("%lld",(X*(deltas/k)%(l/k)+(l/k))%(l/k));
    return 0;
}

4.逆元

若$a\times x\equiv 1(modb)$，就称x是a的逆元。

可以将这个式子转化为$a\times x+b\times y=1$，然后用扩展欧几里得定理求解。

当然也有一种线性算法，在需要求连续逆元时是最优的算法。

以下内容来自https://www.luogu.org/blog/zjp-shadow/cheng-fa-ni-yuan

首先我们有一个, $1^{-1}\equiv 1(\bmod p)$

然后设 $p=k∗i+r,r<i,1<i<p$ ,再将这个式子放到 $\bmod {p}$ 意义下就会得到：

$k∗i+r≡0(modp)$

然后乘上 $i^{-1} , r^{-1}$ 就可以得到:

$k*r^{-1}+i^{-1}\equiv 0 (\bmod p)$

$i^{-1}\equiv -k*r^{-1} (\bmod p)$

$i^{-1}\equiv -\lfloor \frac{p}{i} \rfloor*(p \bmod i)^{-1} (\bmod p)$

模板题：洛谷P3811 【模板】乘法逆元

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

LL n,p,inv[3000005];

int main()
{
    scanf("%d%d",&n,&p);
    inv[1]=1;
    printf("%d\n",inv[1]);
    for (int i=2;i<=n;i++)
    {
        inv[i]=-(p/i)*inv[p%i];
        inv[i]=(inv[i]%p+p)%p;
        printf("%d\n",inv[i]);
    }
    return 0;
}

5.中国剩余定理

还是就放一个我看的吧

https://blog.csdn.net/acdreamers/article/details/8050018

例题：洛谷P3868 [TJOI2009]猜数字

可以用裸的中国剩余定理来做，但是要注意必须用快速乘，不然$10^{18}\times 10^{18}$肯定会超范围。

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

LL n,m,k;
LL A[15],B[15];

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

inline void exgcd(LL l,LL r,LL &x,LL &y)
{
    if (r==0) x=1,y=0;
    else
    {
        exgcd(r,l%r,y,x);
        y-=l/r*x;
    }
}

inline LL gcd(LL a,LL b)
{
    if (b==0) return a;
    return gcd(b,a%b);
}

inline LL qmul(LL a,LL b,LL mod)
{
    LL ans=0,k=a,f=1;
    if (k<0) k=-k,f*=-1;
    if (b<0) b=-b,b*=-1;
    while (b)
    {
        if (b&1) ans=(ans+k)%mod;
        k=(k+k)%mod;
        b>>=1;
    }
    return ans*f;
}

inline LL crt()
{
    LL M=1,ans=0;
    for (int i=1;i<=k;i++) M*=B[i];
    for (int i=1;i<=k;i++)
    {
        LL x,y,Mi=M/B[i];
        exgcd(Mi,B[i],x,y);
        x=(x%B[i]+B[i])%B[i];
        ans=(ans+qmul(qmul(Mi,x,M),A[i],M))%M;
    }
    return (ans<0)?ans+M:ans;
}

int main()
{
    k=read();
    for (int i=1;i<=k;i++) A[i]=read();
    for (int i=1;i<=k;i++) B[i]=read();
    for (int i=1;i<=k;i++) A[i]=(A[i]%B[i]+B[i])%B[i];
    printf("%lld",crt());
    return 0;
}

6.素数筛

普通筛法

inline void getprime()
{
    memset(ss,true,sizeof(ss));
    int cnt=1;
    ss[0]=ss[1]=false;
    for (a=2;a<=sqrt(n);a++)
    {
        if (ss[a]) zs[cnt++]=a;
        for (b=2;b<=n/a;b++) ss[a*b]=false;
    }
}

线性筛

可以很容易的想到，普通筛法中筛了很多重复的数。而线性筛法可以避免重复。主要思路是运用得到了的素数来标记后面的合数。

inline void getprime()
{
    memset(ss,true,sizeof(ss));
    ss[0]=ss[1]=false;
    for (int i=2;i<=n;i++)
    {
        if (ss[i]) zs[cnt++]=i;
        for (int j=1;j<cnt && zs[j]*i<=n;j++) 
        {
            ss[zs[j]*i]=false;
            if (i%zs[j]==0) break;
        }
    }
}

以上内容更新于2018.5.9

线性筛法错误修正于2018.7.28

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
This work is licensed under a CC BY-NC-SA 4.0 International License.
本文链接：https://llf0703.com/p/number-theory.html