数论总结

本文最后更新于：2024年3月7日下午

想着把所有内容都放在模板补全计划里势必会造成文章繁多难受，便新开一档
高中阶段曾经学习过一些，不过大多早已忘却，于今日开始补完
从基础的开始

快速乘

在遇到乘法两个数都很大的情况下，需要通过快速乘来保证在计算过程中间不会溢出
网上有多种快速乘方式，我在此仅提供一种

inline long long mul(long long x,long long y)
{
	long long z=(long double)x/p*y;
	return ((unsigned long long)x*y-(unsigned long long)z*mod+mod)%mod;
}

z就是 $\lfloor x \times y / mod \rfloor$ ,而我们要求的 $x \times y \% mod$ 实际上与 $x \times y - \lfloor x \times y / mod \rfloor \times mod$ 是等价的
而unsigned long long 保证了就算溢出， $x \times y$ 和 $\lfloor x \times y / mod \rfloor \times mod$ 的差值还是不变，因此即使溢出最后的结果仍然不变。时间复杂度 O(1)

~~(latex好麻烦，大幅度降低写文效率. . .)~~

快速幂

很简单的原理，在此不做过多叙述
chty的一行快速幂：
long long fast(long long a,long long b){long long ans=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ans=mul(ans,a);return ans;}
（syq学长好强啊

GCD

这个也算是入门级别的
inline long long gcd(a,b){return !b?a:gcd(b,a%b);}

拓展GCD

裴蜀定理：丢番图方程（二元一次，下同）$ a \times x + b \times y = m $有解当且仅当$ m | ( a , b )$

扩展gcd就是在求丢番图方程$ a \times x + b \times y =gcd(a,b) $的整数解
证明：
$ a \times x_1 + b \times y_1 = gcd(a,b) $
$ b \times x_2 + (a \% b) \times y_2 = gcd(b,a \% b)$
$ 因为 gcd(a,b) = gcd(b,a \% b) $
$ 得 a \times x_1 + b \times y_1 = b \times x_2 + ( a \% b ) \times y_2 = b \times x_2 + ( a - a / b \times b ) \times y_2 = a \times y_2 + b \times (x_2 - a / b \times y_2 ) $
$ 所以x_1=y_2,y_1=x_2-a/b \times y_2$
$ 末状态：b=0,a = gcd(a,b)时，gcd(a,b) \times x=gcd(a,b),得x = 1$
代码如下：

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

欧拉函数

对于一个正整数n，小于n且和n互质的正整数（包括1）的个数叫做欧拉函数，记作 $\phi(n)$ 。

一个很简明的想法是在1~n中找到n的约数，然后减去约数在n之内的倍数即可。
例：若n=12，呢么分解质因数则为$ 12 = 2 \times 2 \times 3 $
但是不能直接减12/2和12/3，因为会有6这个2，3的公倍数被减了两次
运用容斥的原理，我们可得一种简单的方法，令$ phi(n) = n \times \prod_{i=1}^k (1 - a_i)$(a是n因子的集合，k为a因子的个数)
直接分解质因数的复杂度会达到$ O(\sqrt n)$,求单个数时可用，但求n个数的欧拉函数时说不可用的
在求n个数的欧拉函数时，我们可以利用类似筛法的方式求得

long long phi[Maxn+10];
void Euler()
{
    phi[1]=1;
    for(int i=2;i<n;i++)
    {
        if(!phi[i])
        {
            for(int j=i;j<n;j+=i)
            {
                if(!phi[j]) phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
        }
    }
}

一些性质：

欧拉函数是积性函数——若m,n互质，$ \phi(mn) = \phi(m) \times \phi(n) $
p为质数 $ \phi(p) = p-1 $ 因为质数p除了1以外的因数只有p
如果 $ i \% p = 0 $, 那么 $ \phi(i \times p) = \phi(i) \times p $
若 $ i \% p ≠ 0 $, 那么$ \phi( i \times p ) = \phi(i) \times ( p - 1 ) $
如果n是素数，k是正整数，那么 $ \phi( n ^ k ) = (n-1) \times n^{k-1} $

由这些性质，我们可以将复杂度进一步优化到$ O(n) $递推

long long phi[MaxN+10], prime[MaxN+10];
void Euler()
{
    phi[1]=1;
    for(int i=2;i<N;++)
    {
        if(!phi[i])//第二条性质
        {
            phi[i]=i-1;
            prime[prime[0]++]=i;
        }
        for(int j=0;j<prime[0]&&1ll*i*prime[j]<N;j++)
        {
            if(i%prime[j])phi[i*prime[j]]=phi[i]*(prime[j]-1);//第三条性质
            else
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;//优化成线性复杂度
            }
        }
    }
}

乘法逆元

对于正整数a和m，如果$ a \times x \% m=1 $, 则x的最小正整数解称为a模m的逆元，表示为$ a ^{-1} (mod m)$

（1）根据费马小定理：有$ a^{m-1} \% m = 1 $, 即$ a \times a^{m-2} \% m = 1 $, 所以$ a ^{m-2} $就是a模m的逆元。（适用条件：m为素数）
（2）扩展欧几里得求解：$ a \times x \% m = 1 $,即$ a \times x - m \times y = 1 $,解这个丢番图方程即可。(适用条件：gcd(a,m)=1)
（3）欧拉定理：若 $ gcd(a,m) = 1 $，则 $ a^{ \phi(m)} ≡ 1 (mod m) $
$ a^{-1}=a^{\phi(m)-1}$，使用欧拉函数+快速幂计算，复杂度同费马，但较费马而言，模数m可以不为质数，因此应用范围广一点
（4）线性递推：
规定m为质数，且$ 1^{-1} ≡ 1(mod m) $ 设 $ m = k \times a + b (b < a , 1 < a < m ) $,即$ k \times a + b ≡ 0(mod m) $
两边同时乘以$ a^{−1} \times b^{−1} $，得到 $ k \times b^{−1} + a^{−1} ≡ 0 (mod m) $
$ a^{-1} ≡ − k \times b^{−1} (mod m) $
$ a^{−1} ≡ − m / a \times ( m \% a )^{-1} (mod m) $
从头开始扫一遍即可，时间复杂度O(n) （适用条件：m为素数）

1 2	`inv[1]=1; for(int i=2;i<=n;i++) inv[i]=(mod-(mod/i))*inv[mod%i]%mod;`

中国剩余定理

假设整数 $ m_1,m_2,m_3…$ 两两互素，则对于任意的整数 $ a_1,a_2,a_3…$ ，方程组

$\begin{cases} & x \equiv a_1 (mod m_1) \\\\ & x \equiv a_2 (mod m_2) \\\\ & x \equiv a_3 (mod m_3) \\\\ & . . . \\\\ \end{cases}$

都存在整数解.
若多个数 $x_1,x_2...$ 满足该方程，则必有 $x_i \equiv x_j (mod M)$ ，其中 $M = \prod_{i=1}^n m_i$
因此x在MOD M下有唯一解。
解为： $x\equiv (a_1 M_1 M_1^{-1} + a_2 M_2 M_2^{-1} +...+a_n M_n M_n^{-1}) (mod M)$
其中 $M_i = M / m_i , M_i^{-1}$ 为 $M_i$ 膜 $m_i$ 的逆元。

lucas定理快速求组合数

适用于求解组合数取模问题，n较为大不能用阶乘计算且要求mod较小

$C_n^m \% mod = (C_{\frac{n}{mod}}^{\frac{m}{mod}}*C_{n\%mod}^{m\%mod})\%mod$

lucas复杂度 $O(log_{p}(n)*p)$
具体证明见此，不过直接用就好了。

#include<bits/stdc++.h>
using namespace std;
const long long N = 1e6;
long long n,m,p,A[N+5],B[N+5];
long long C(long long n,long long m,long long p)
{return (m>n)?0:((long long)A[n]*B[n-m]%p*B[m]%p);}
inline long long Lucas(long long n,long long m,long long p)
{return (!m)?1:((long long)C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p);}
int main()
{
    scanf("%d%d%d", &n, &m, &p);
    A[0]=B[0]=A[1]=B[1]=1;
    for(int i=2;i<=p;i++)B[i]=-(long long)(p/i)*B[p%i]%p;
    for(int i=2;i<=p;i++)A[i]=(long long)A[i-1]*i%p,B[i]=(long long)B[i-1]*B[i]%p;
    printf("%d\n", (Lucas(n, m, p)+p)%p);
    return 0;
}

Meisell-Lehmer算法计算大范围素数个数

Meisell-Lehmer算法是计算超大范围内素数个数的一种算法，原理中文网上资料甚少. . .导致只有代码.附有wiki链接，能看懂的老兄可以去试着看看，需要用不存在的工具查看。
测试计算极限为 $10^{11}$

#include<bits/stdc++.h>
#define MAXN 100    // pre-calc max n for phi(m, n)
#define MAXM 10010 // pre-calc max m for phi(m, n)
#define MAXP 40000 // max primes counter
#define MAX 400010    // max prime
#define setbit(ar,i) (((ar[(i) >> 6]) |= (1 << (((i) >> 1) & 31))))
#define chkbit(ar,i) (((ar[(i) >> 6]) & (1 << (((i) >> 1) & 31))))
#define isprime(x) (((x)&&((x)&1)&&(!chkbit(ar,(x))))||((x) == 2))
using namespace std;
long long dp[MAXN][MAXM];
unsigned int ar[(MAX>>6)+5]={};
int len = 0,primes[MAXP],counter[MAX];
void Sieve()
{
    setbit(ar,0),setbit(ar,1);
    for(int i=3;(i*i)<MAX;i++,i++)
        if (!chkbit(ar,i))
        {
            int k=i<<1;
            for(int j=(i*i);j<MAX;j+= k) setbit(ar, j);
        }
    for(int i=1;i<MAX;i++)
    {
        counter[i]=counter[i-1];
        if(isprime(i))primes[len++]=i,counter[i]++;
    }
}
void init()
{
    Sieve();
    for(int i=0;i<MAXN;i++)
        for(int j=0;j<MAXM;j++)
        {
            if (!i) dp[i][j]=j;
            else dp[i][j]=dp[i-1][j]-dp[i-1][j/primes[i-1]];
        }
}
long long phi(long long m, int n)
{
    if(n==0) return m;
    if(primes[n-1]>=m)return 1;
    if(m<MAXM&&n<MAXN)return dp[n][m];
    return phi(m,n-1)-phi(m/primes[n-1],n-1);
}
long long Lehmer(long long m)
{
    if(m<MAX)return counter[m];
    long long w,sum=0;
    int a,s,c,x,y;
    s=sqrt(0.9 + m),y=c=cbrt(0.9+m);
    a=counter[y],sum =phi(m,a)+a-1;
    for (int i=a;primes[i]<=s;i++) sum=sum-Lehmer(m/primes[i])+Lehmer(primes[i])-1;
    return sum;
}
int main()
{
    init();
    long long int n;
    while(scanf("%lld",&n)!=EOF)printf("%lld\n",Lehmer(n));
    return 0;
}

算法数论总结

acm 技巧数论

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

数论题目 GCD 上一篇

博客创建历程(记录向) 下一篇

快速乘

快速幂

GCD