基础数论学习总结

@Llf  May 9, 2018

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


1.整除

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

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

2.同余

同余性质:

  1. 自反性 $a\equiv a(mod m) $
  2. 对称性 若 $a\equiv b(mod m)$, 则 $b\equiv a(mod m)$
  3. 传递性 若 $a\equiv b(mod m),b\equiv c(mod m)$,则 $a\equiv c(mod m)$
  4. 同加性 若 $a\equiv b(modm)$,则 $a+c\equiv b+c(modm)$
  5. 同乘性 若 $a\equiv b(modm)$,则 $a\times c\equiv b\times c(modm)$
    若 $a\equiv b(modm),c\equiv d(modm)$,则 $a\times c\equiv b\times d(modm)$
  6. 同幂性 若 $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(mod p)$

然后设 $p=k\times i+r,r<i,1<i<p$ ,再将这个式子放到 $mod p$ 意义下就会得到:

$k\times i+r\equiv 0(modp)$

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

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

$i^{-1}\equiv -k\times r^{-1} (mod p)$

$i^{-1}\equiv -\lfloor \frac{p}{i} \rfloor \times (p mod i)^{-1} (mod 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;
    }
}

以上内容更新于2018.5.9



添加新评论

  1. %%% 太强了!

    Reply
  2. #大佬#
    您太强了

    Reply
  3. 您为什么不写莫比乌斯反演啊?

    ~~肯定是您不屑于写~~

    Reply
    1. Llf
      @larryzhong

      我一个蒟蒻怎么可能会这个,zzh大佬您太强辣,还有duanyll大佬也太强辣
      还有typecho应该是支持评论md的,估计是这个主题给阉割了,我有时间魔改一下

      Reply