2024TJUACM第三讲——数论

2024-01-20

字数统计: 3.4k | 阅读时长≈ 14 分钟

讲讲数论

数论基础

NT-1 质数相关

质数筛法：欧拉线性筛

算法原理： $对于一个合数进行质因数分解得到对于素数筛去的时候，我们只要这个合数被最小的质数筛去而在素数统计的时候，我们就是按照从小到大的顺序进行统计的考虑埃氏筛法的过程，如果一个数是质数，那么他的倍数一定是合数；如果一个数是合数，那么其倍数依旧是合数接下来证明欧拉线性筛是如何避免埃氏筛法中明显存在的重复筛去问题的。在开始前需要先区分筛除素数倍数即和用素数即筛的区别。对于一个发现的目标质数，我们要将其存储并筛掉其的所有倍数首先就思考的是，筛倍数的时候为什么只筛素数倍？显然，根据分解质因数定理易得，任何一个合数都会有一个最小素数将其筛除，筛素数倍就是分解质因数的逆过程第二个问题，为什么只筛除比自己小的素数倍数？设当前素数为如果筛除比自己大的素数倍数，设为即筛除倍，那么在筛素数倍时会再次出现素数筛除倍。这样就会出现大量的重复。而且不符合用最小的素数筛除原则第三个问题，为什么在筛倍数时维护时首先在此时肯定是合数，如果前面小的素数出现了那么必有此时设紧随其后的一个质数为会在筛时被倍筛除掉。综上所述，线性性成立，时间复杂度$

int prime[maxn];
bool vis[maxn];//初始0，标记合数
void euler(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prime[++prime[0]]=i;
        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=true;//筛去合数
            if(i%prime[j]==0)break;
        }
    }
}

积性函数

定义

若函数满足且都有，则为积性函数。

特别的，若都有,则称作完全积性函数。

性质

若和均为积性函数，那么下列函数也称作积性函数：设质因数分解，则

若为积性函数，则

若为完全积性函数，则

（因为质数和其自己的并不是1而是其本身）

常见积性函数

欧拉函数.

除数函数

（特别的，又记作，表示除数的个数。又记作，表示因数和）

二者均为非完全积性函数。

莫比乌斯函数

欧拉函数

通解公式

性质

若，则
若,则

仔细观察不难发现2是4的子集关系，故性质1、3、4称作欧拉函数三性质，简称欧拉函数性。

线性筛法求积性函数

假设一个积性函数满足：对于任意的质数和正整数,可以在的时间内计算,那么可以在的时间内筛出的值。

设合数的质因数分解为单调递增,我们根据如下定义最小质因子之幂函数 $若可以被筛除，那么满足如下的递推式$ 那么显然有如下式子必定成立：若,则说明就是某个质数的次幂，可以计算；否则，

显然此时问题转化成了求某质数的最小质因子，而欧拉筛恰好就是根据这个过程来做到线性筛除的。

int prime[maxn];
bool vis[maxn];
int f[maxn];
int g[maxn];
void euler(int n)
{
    g[0]=0;
    g[1]=0;
    for(int i=2;i<=maxn;i++)
    {
        if(!vis[i])
        {
            prime[++prime[0]]=i;
            g[i]=i;
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=true;//合数标记
            if(i%prime[j])
            {
                g[i*prime[j]]=g[i]*prime[j];
                break;
            }
            g[i*prime[j]]=prime[j];
        }
    }
}
int query(int x)
{
    if(x==g[x])return f[x];
    return query(x/g[x])*query(g[x]);
}

事实上，对于的计算很多时候不方便达到（比如说最经典的欧拉函数，其并没有那么的好计算，因为在线性筛法中不会特别的标注的合数）。此时就可以通过欧拉函数性来进行简化操作。

换言之，如果一个积性函数能够满足以下三条性质：

$可查询$
若，则
若,则 $可积性转移$ （即递推公式只含有乘法）

则均可使用线性筛实现线性求解。

下列是欧拉函数筛法例子

int prime[maxn];
bool vis[maxn];//初始0，标记合数
int phi[maxn];
void euler(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prime[++prime[0]]=i,phi[i]=i-1;\\性质1
        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=true;\\筛去合数
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=prime[j]*phi[i];\\性质3
                break;
            }
            phi[i*prime[j]]=phi[prime[j]]*phi[i];\\性质2
        }
    }
}

下例是所需要的积性函数 $函数表示是平方数时的最小$ 我们探寻其是否符合欧拉函数性。

，显然。因为不可能有更小的数满足条件了。
，互质没有公约数，只能各自配对成平方数后自行配对。
若，此时有，积性化转移。

综上所述，可以使用欧拉筛解决。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2e5+10;
int num[maxn],f[maxn],prime[maxn];
bool vis[maxn];
void init()
{
    f[0]=f[1]=1;
    for(int i=2;i<=2e5;i++)
    {
        if(!vis[i])
        {
            prime[++prime[0]]=i;
            vis[i]=1;
            f[i]=i;
        }
        for(int j=1;j<=prime[0]&&i*prime[j]<=2e5;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                f[i*prime[j]]=f[i/prime[j]];
                break;
            }
            f[i*prime[j]]=f[i]*f[prime[j]];
        }
    }
    return;
}
int a[maxn];
signed main()
{
    init();
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i],num[a[i]]++;
    long long ans=0;
    for(int i=1;i<=2e5;i++)
    {
        if(!num[i])continue;
        for(int p=1;p<=450&&p*p*f[i]<=2e5;p++)
        {
            if(p*p*f[i]!=i)
            ans+=num[i]*num[p*p*f[i]];
        }
    }
    ans/=2;
    for(int i=0;i<=2e5;i++)
    {
        if(num[i]>1)
        ans+=num[i]*(num[i]-1)/2;
    }
    ans+=num[0]*(n-num[0]);
    cout<<ans<<endl;
    system("pause");
    return 0;
}

NT-2 约数相关

最大公约数:

欧几里得算法

int gcd(int x,int y)
{return y==0? x : gcd(y,x%y); }

大整数求模运算时间复杂度过高，建议换用更相减损术（最坏情况)。

int gcd(int x,int y)
{
    if(x>y)swap(x,y);
    return y==0?x:gcd(y,y-x);
}

对于远大于的情况，对更相减损术使用Stein算法优化：

若则有

否则若,则有

否则

最小公倍数

最小公倍数算法

扩展欧几里得算法

求解方程的一组可行解。

算法原理： $设方程的一组可行解为则有又因为所以由于故有方程化简有所以有$

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

此时求解到的和为一组特解 $，$ 。一般的该方程的解系为

裴蜀定理

$设不全为的整数，对于任意整数有且一定存在整数解使得下列方程成立$

NT-3 同余相关

费马小定理与欧拉定理

费马小定理

$对于任意正整数，满足则必然有以下同余式成立$

证明

$设一个和互质的质数为，勒令集合的完全剩余系由于那么显然进一步的，则必然有使得剩余系的互质倍数亦为剩余系那么显然会有以下的内容成立记则$

关于剩余系、完全剩余系、简化（既约）剩余系、同余类的概念

欧拉定理

$对任意正整数、，若，则有$

证明：

$设集合为模下的一个简化剩余系，那么易得同样是一个简化剩余系则根据费马小定理的证明方法有$

欧拉定理与扩展欧拉定理

证明，

扩展欧拉定理应用于对超大整数快速幂求模的优化降幂运算，来大幅度降低时间复杂度

#define int long long
int prime[maxn];
bool vis[maxn];//初始0，标记合数
int phi[maxn];
void euler(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])prime[++prime[0]]=i,phi[i]=i-1;\\性质1
        for(int j=1;j<=prime[0]&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=true;\\筛去合数
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=prime[j]*phi[i];\\性质3
                break;
            }
            phi[i*prime[j]]=phi[prime[j]]*phi[i];\\性质2
        }
    }
}
int qpow(int a, int n, int MOD) // 快速幂
{
    int ans = 1;
    while (n)
    {
        if (n & 1)
            ans =  ans * a % MOD; 
        n >>= 1;
        a =  a * a % MOD;
    }
    return ans;
}
int Ex_euler_T(int a,int n)
{
    if(__gcd(a,MOD)==1)
    {
        return qpow(a,b%phi[m]);
    }
    else
    {
        if(b<phi[m])
        {
            return qpow(a,b);
        }
        return qpow(a,(b%phi[m])+phi[m]);
    }
}
#undef int

乘法逆元

如何求解分数的模？换言之，已知，如何求?

扩展欧几里得定理求解

方程极易转化为，依据扩展欧几里得公式迅速求解。

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

一般的我们需要最小的正整数解：

int invq(int a,int mod)
{
 int x,y;
 exgcd(a,mod,x,y);
 return (x%mod+mod)%mod;
}

费马小定理求解
这个是最常用的，一般题目都会让对质数求模。
```
int invq(int a)
{
 return quickpow(a,mod-2);
}
```
逆元运算是分数意义的求模，在整数域定义了实数意义上的倒数运算，其基本性质和倒数没有区别。根据此可由前缀积实现线性求个数的逆元。

线性同余方程

解方程：

威尔逊定理

NT-S-1 线性同余方程组与中国剩余定理

中国剩余定理

今有物不知几何，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

中国剩余定理与线性同余方程组

数学抽象

一般的，中国剩余定理可以求解如下线性同余方程组

其中所有互质。

求解过程

计算
对于第个方程:
1. 计算
2. 计算
3. 计算，对取模。
方程组在模意义下唯一解为

证明

$当时，故有$

实现

#include <bits/stdc++.h>
using namespace std;
#define int long long
void Exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return;
    }
    Exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return;
}
const int maxn = 101;
int m;
int n[maxn], a[maxn]; // 对a取模余数是b
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> m;
    int N = 1;
    for (int i = 1; i <= m; i++)
    {
        cin >> n[i] >> a[i];
        N *= n[i];
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
    {
        int tar = N / n[i];
        int x, y;
        Exgcd(tar, n[i], x, y);
        x = (x % n[i] + n[i]) % n[i];
        (ans += ((tar * x) % N * (a[i] % N))) %= N;
    }
    cout << (ans + N) % N << endl;
    system("pause");
    return 0;
}

扩展中国剩余定理与扩展欧几里得定理

此时之间不保证两两互质，无法使用中国剩余定理的逆元方法求解。

求解方法

任取两组方程设此时方程组某个解为（ $、$ ，不保证必须为质数）

那么可以将等式转化为根据裴蜀定理，如果，那么此时该方程无解,同余方程组无解。

否则可计算出其中，再次应用裴蜀定理

求解之后得到特解（注意，可能是负的） 组合得到新同余方程如上应用次扩展欧几里得定理之后即可得到同余方程组结果。

快速乘

需要注意的是，在线性同余方程组求解中，可能会非常的大以至于爆破，而且计算机做加法的速度远快于做乘法。所以需要类比快速幂使用快速乘法。需要注意的是，在本题特殊环境下，可能出现负数的快速乘，需要对模化成正数解决。

#define int long long
int quickmul(int a,int b,int mod)
{
    int e=0;
    while(b)
    {
        if(b&1)(e+=a)%=mod;
        (a<<=1)%=mod;
        b>>=1;
    }
    return e;
}
#undef int

解决方案

#include <bits/stdc++.h>
using namespace std;
#define int long long
int quickmul(int a, int b, int mod)
{
    while (a < 0)
        a += mod;
    while (b < 0)
        b += mod;
    if (a < b)
        swap(a, b);
    int e = 0;
    while (b)
    {
        if (b & 1)
            (e += a) %= mod;
        (a <<= 1) %= mod;
        b >>= 1;
    }
    return e;
}
void exgcd(int a, int b, int &x, int &y)
{
    if (b == 0)
    {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
}
const int maxn = 500001;
int a[maxn], m[maxn]; // 对m取模余数是a
int n;
int ExCRT()
{
    int mod = m[1], ans = a[1];
    for (int i = 2; i <= n; i++)
    {
        int b1 = mod, b2 = m[i], c = __gcd(b1, b2), minus = (a[i] - ans % b2 + b2) % b2;
        if (minus % c != 0)
            return -1;
        b1 /= c, b2 /= c, minus /= c;
        int x, y;
        exgcd(b1, b2, x, y);
        x = quickmul(x, minus, b2);
        ans += x * mod;
        mod *= b2;
        ans = (ans % mod + mod) % mod;
    }
    return ans;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> m[i] >> a[i];
    }
    cout << ExCRT() << endl;
    system("pause");
    return 0;
}

NT-S-2 卢卡斯定理与扩展卢卡斯定理

卢卡斯定理

内容

$对于质数，有如下等式成立$

亦或写作注意到可能依旧很大，可继续使用卢卡斯定理递归求解。边界条件为返回.

long long C(long long n,long long m,long long mod)
{
    if(m>n&&n==0)return 0;
    if(m==0)return 1;
    return ((frac[n]*invq[m]%mod)*invq[n-m])%mod;
}
//阶乘的值和逆元预处理是线性的递推
long long Lucas(long long n, long long m, long long p)
{
    if (m == 0)
        return 1;
    return (C(n % p, m % p, p) * Lucas(n / p, m / p, p)) % p;
}

证明

扩展卢卡斯定理

版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！