数论学习笔记

· · 个人记录

前言

最近学习了数论，教练要求写博客整理学习内容。写在这里，一方面方便自己以后复习，另一方面给其他人参考。顺带一提，数论真的让人头晕。

部分内容来自百度百科。

数论基础

若 d\mid a ，则有 a=dk

如果 d\mid a ，则称 a 是 d 的倍数，d 是 a 的约数。

一个整数 a 的约数最小是 1 ，最大是 \mid a\mid 。

模 n 等价类：表示对 n 取模后得数相同的整数集合,记作 [a]_{n} 。

例：[a]_{7}=\{...,-11,-4,3,10,17...\}

b\in[a]_n$ 等同于 $b=a\;(mod\;n)

注意：-1 = n-1\;(mod\;n)

素数筛

素数:素数数是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数，也叫质数。

素数判定:

bool Isprime(int a)
{
    if(a==1||a==0)return 0;
    for(int i=2;i*i<=a;i++)
        if(a%i==0)return 0;
    return 1;
}

由于因数是成对出现的，所以只需要枚举到平方根即可，时间复杂度为 O(\sqrt{n}) 。事实上，这个复杂度足以应付很多问题。

当数据范围达到 10^6,10^7 甚至更大时，单个判定质数一般就会超时。

埃氏筛：要得到自然数 N 以内的全部素数，必须把不大于 \sqrt{N} 的所有素数的倍数剔除，剩下的就是素数。

例题：

P3912 素数个数

模板：

int eratosthenes(bool a[],int n)
{
  int cnt=n-1;
  a[1]=1;
  for(int i=2;i*i<=n;i++)
     if(!a[i])
       {
       for(int j=i*2;j<=n;j+=i)
         {
         if(!a[j])
            {
             a[j]=1;
             cnt--; 
             }
         }
       }
  return cnt;
}

给出要筛数值的范围 N ，找出以内的素数。先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉；再用下一个质数，也就是 3 筛，把 3 留下，把 3 的倍数剔除掉；接下去用下一个质数 5 筛，把 5 留下，把 5 的倍数剔除掉；不断重复下去，最后得到答案。

时间复杂度: O(n\log\log n)

欧拉筛：让自然数 N 以内所以的数被其最小的素因子筛除，剩下的就是素数。

例题：

P3383 【模板】线性筛素数

模板：

int n,pri[7000000];
bool a[70000000];
int linear(bool a[],int pri[],int n)
{
    int cnt=0;
    a[1]=1;
    for(int i=2;i<=n;i++)
        {
            if(!a[i])pri[cnt++]=i;
            for(int j=0;j<cnt&&i*pri[j]<=n;j++)
                {
                    if(!a[i*pri[j]])a[i*pri[j]]=1;
                    if(i%pri[j]==0)break;
                }
        }
    return cnt;
}

引用教练PPT上的一张图：

时间复杂度 O(n)

欧拉函数

欧拉函数：对正整数 N ，欧拉函数是小于 N 的正整数中与 N 互质的数的数目，记作 \varphi(N) 。

欧拉函数的性质：

1$：$\varphi(1)=1 $3$：$\varphi(p^k)=p^k-p^{k-1}=(p-1)*p^{k-1} 4$：欧拉函数是**积性函数**，若$m,n$互质则有 $\varphi(m*n)=\varphi(m)*\varphi(n) ![](https://cdn.luogu.com.cn/upload/image_hosting/6qzu0s1z.png) $6$：对于任意的 $n=p_{1}^{k_{1}}\times p_{2}^{k_{2}}\times p_{3}^{k_{3}}\times ... \times p_{r}^{k_{r}}$（其中 $p_{1}^{k_{1}},p_{2}^{k_{2}},p_{3}^{k_{3}},...p_{r}^{k_{r}}$ 为 $n$ 的不同素因子），则有 $$\varphi(n)=n\times\prod_{i=1}^r(1-{\frac 1 {p_{i}}})$$ 欧拉函数的两种求法 单求： ```cpp int eulerfun(int a) { int ans=a; for(int i=2;i*i<=a;i++) if(a%i==0) { ans=ans/i*(i-1); while(a%i==0) a/=i; } if(a!=1)ans=ans/a*(a-1); return ans; } ``` 时间复杂度 $O(\sqrt{n})

求前N项的欧拉函数：（类似线性筛）

int n,pri[1000001],f[1000001];
bool a[1000001];
int linear(bool a[],int pri[],int n)
{
    int cnt=0;
    a[1]=1;f[1]=1;
    for(int i=2;i<=n;i++)
        {
            if(!a[i])
                {
                pri[cnt++]=i;
                f[i]=i-1;
                }
            for(int j=0;pri[j]<=n/i;j++)
                {
                    a[i*pri[j]]=1;
                    if(i%pri[j]==0)
                      {
                      f[i*pri[j]]=f[i]*pri[j];
                      break;
                      }
                    f[i*pri[j]]=f[i]*(pri[j]-1);
                }
        }
    return cnt;
}

时间复杂度 O(n)

欧拉函数的运用

例题：

P2158 [SDOI2008]仪仗队

把题目简化一下，就是求横，纵坐标 \gcd 为 1 的数，也就是互质的数的对数，自然想到欧拉函数处理互质数对数，然后求和。

所以就推出这个式子：

\sum_{k=1}^{n-1} \varphi(k) 
#include <bits/stdc++.h>
using namespace std;
int n,pri[1000001],f[1000001];
bool a[1000001];
int linear(bool a[],int pri[],int n)
{
    int cnt=0;
    a[1]=1;f[1]=1;
    for(int i=2;i<=n;i++)
        {
            if(!a[i])
                {
                pri[cnt++]=i;
                f[i]=i-1;
                }
            for(int j=0;pri[j]<=n/i;j++)
                {
                    a[i*pri[j]]=1;
                    if(i%pri[j]==0)
                      {
                      f[i*pri[j]]=f[i]*pri[j];
                      break;
                      }
                    f[i*pri[j]]=f[i]*(pri[j]-1);
                }
        }
    return cnt;
}

int main()
{
    long long ans=0;
    scanf("%d",&n);
    if(n==1)
       {
       printf("0");
       return 0;
       }
    linear(a,pri,n-1);
    for(int i=1;i<=n-1;i++)
        ans+=f[i];
    printf("%lld",ans*2+1);
    return 0;
}

P1390 公约数的和

这题可以想象成是类似仪仗队那题的矩阵，然后套等差数列求和公式即可。

#include <bits/stdc++.h>
using namespace std;
long long n,pri[100000001],f[100000001];
bool a[100000001];
int linear(bool a[],long long pri[],long long n)
{
    int cnt=0;
    a[1]=1;f[1]=1;
    for(int i=2;i<=n;i++)
        {
            if(!a[i])
                {
                pri[cnt++]=i;
                f[i]=i-1;
                }
            for(int j=0;pri[j]<=n/i;j++)
                {
                    a[i*pri[j]]=1;
                    if(i%pri[j]==0)
                      {
                      f[i*pri[j]]=f[i]*pri[j];
                      break;
                      }
                    f[i*pri[j]]=f[i]*(pri[j]-1);
                }
        }
    return cnt;
}

int main()
{
    long long ans=0;
    scanf("%d",&n);
    linear(a,pri,n);
    for(int i=1;i<=n;i++)
        ans+=(long long)f[i]*((1+n/i)*(n/i)/2);
    printf("%lld",ans-(1+n)*n/2);
    return 0;
}

欧拉定理

模 n 的既约剩余系：模 n 的既约剩余系是由 \varphi(n) 个整数构成的集合，集合中每个元素均与 n 互素，且任意两个数模 n 不同余。

模 n 的既约剩余系的性质：

模 n 的既约剩余系中每一个数乘以与 n 互素的一个数，每个数模 n 后还是一个模 n 的既约剩余系。

例：

**欧拉定理**：设 $m$ 是一个正整数，$a$ 是一个整数且 $\gcd(a,m)=1$ ，那么 $a^{\varphi(m)}\equiv1(mod\;m)$ 。 ### 欧几里得算法与扩展欧几里得算法 **最大公约数**：最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个，记作 $\gcd(a,b)$ 。 **互质数**：两个或多个整数的公因数只有1的非零自然数。公因数只有1的两个非零自然数，叫做互质数。 欧几里得算法 模板 ```cpp int gcd(int a,int b) { if(b==0)return a; else return gcd(b,a%b); } ``` 实际上就是辗转相除法，还有辗转相减法，不过没有辗转相除法快。 $\gcd$ 的推论：（此处$\mid$作整除符号） $1$：对于任意整数 $a\mid b$ ，如果 $d\mid a$ 并且 $d\mid b$ ，则 $d\mid \gcd(a,b) 2$：$\gcd(an,bn)=n\times\gcd(a,b) 3$：对于正整数 $a,b,n$ ，若 $n\mid ab$ 并且 $\gcd(a,n)=1$ ，则 $\gcd(b,n)=1

扩展欧几里得算法

给定一个关于未知数 x,y 的一次不定方程，求 x,y 的值。

ax+by=c

这个式子也被称之为裴蜀等式。

方程有整数解，当且仅当 c 是 \gcd(a,b) 的倍数，裴蜀等式有解时必然有无穷解。在辗转相除法下任意情况，裴蜀等式均成立。

接下来引用教练PPT上的一幅图：

模板：

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

既可以求出 \gcd ，又可以求出裴蜀等式的 x,y 。

继续引用教练的PPT：

由于扩展欧几里德算法求出的是通解，所以最后结果需要乘以 {\frac c {\gcd(a,b)}} 。

例题：

P1082 [NOIP2012 提高组] 同余方程

由

ax\equiv 1(mod \;b)

得

ax+by=1

然后就转化成了裴蜀等式，扩展欧几里得算法解决。

#include <bits/stdc++.h>
using namespace std;
int n,a,b,x,y; 
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
       {
        x=1;
        y=0;
        return a;
       }
    int r=exgcd(b,a%b,x,y);
    int d=x;
    x=y;
    y=d-a/b*y;
    return r;
}

int main()
{
    scanf("%d%d",&a,&b);
    int r=exgcd(a,b,x,y);
    printf("%d\n",(x+b)%b);
    return 0;
}

对于负数取模的处理方法：（求正整数解）

对于x：((x\times {\frac c {\gcd(a,b)}})\mod {\frac b {\gcd(a,b)}}+{\frac b {\gcd(a,b)}})\mod {\frac b {\gcd(a,b)}}

对于y：((y\times {\frac c {\gcd(a,b)}})\mod{\frac b {\gcd(a,b)}}+{\frac b {\gcd(a,b)}})\mod {\frac b {\gcd(a,b)}}

逆元

还没讲，留个位置。

整除分块

求一个式子：

\sum^{n}_{i=1}\lfloor \frac{n}{i}\rfloor

暴力求法O(n)，代码如下：

long long dib(int n) {
    long long res=0;
    for(int i=1; i<=n; i=i+1) {
        res=(res+n/i);
    }
    return res;
}

但在很多时候，O(n) 是不够用的。

这个时候，就要使用更快的算法——整除分块。

例题：

UVA11526 H(n)

经过观察，发现有许多\lfloor \frac{n}{i}\rfloor的值是一样的，可以通过整除分块把这些数分在一起，成为一个块，用乘法计算，加快运算速度。

设一个数据块左端点的值为r，右端点的值为l，分块数值为k，可得：

r=\lfloor \frac{n}{k}\rfloor

又因为

k=\lfloor \frac{n}{l}\rfloor

所以

r=\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor}\rfloor

有了左端点和右端点，每个块有多少个数也就很好求了。

模板：

long long dib(int x)
{
    long long ans=0,j=1;
    if(x==0)return 0;
    for(long long i=1;i<=x;i=j+1)
        {
        j=x/(x/i);
        ans+=(j-i+1)*(x/i);
        }
    return ans;
}

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

后记

还没讲完， 讲完再记。