当前位置：首页 > news >正文

一名提高选手的数论之路（二）

news 来源：原创 2024/5/8 2:24:25

1.乘法逆元（inv）两种求法：
First:（满足p为质数且a与p互质才可以使用）
根据费马小定理：ap≡a(modp)
可得ap−2≡a−1(modp)
由此可知，ap−2modp即是a在模p意义下的逆元
然而ap−2可以轻易用快速幂算出
Second:（无条件）
通过扩展欧几里得算法来求：exgcd(a,p,x,y)
如此调用，x便是求得的a在模p意义下的逆元
不要问我为什么，我不想（zhi）说（dao）
记得答案是这样的(x+p)%p，因为要防止求出负数
代码就不用了吧。

2.在O(n)内求前n个逆元：
这是偶然从一个人的博客里看见的。
首先inv[1]=1
然后inv[i]=(M-M/i)*inv[M%i]%M
如此从2一直递推到n就可以了。
具体证明可以看出处
代码很简单：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
int n,M;
int inv[100001];
int main(){
    scanf("%d %d",&n,&M);
    inv[1]=1;
    for(int i=2;i<=n;i++){
        inv[i]=(M-M/i)*inv[M%i]%M;
    }
    for(int i=1;i<=n;i++){
        printf("%d ",inv[i]);
    }
    return 0;
}

3.Lucas定理：（注意，在算阶乘数组的时候，必须从a[0]开始初始化，不然有可能错。）
这个定理是用来求大组合数取模的结果的。
具体证明呀什么的可以自己百度。
我这里给个公式：
C(n,m)=C(n%p,m%p)*C(n/p,m/p)
然后在计算的时候，只要递归地去计算右半部分就可以了，左半部分可以预处理出阶乘直接算，记得边算边取模就好。

//这是洛谷的模板题
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
ll ksm(ll a,ll b,ll p){
    a%=p;
    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%p;
        }
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
ll a[100001];
ll cm(ll n,ll m,ll p){
    if(m>n)return 0;
    return (a[n]*(ksm(a[m],p-2,p))%p*(ksm(a[n-m],p-2,p))%p);
}
ll lucas(ll n,ll m,ll p){
    if(m==0)return 1;
    return (cm(n%p,m%p,p)%p*lucas(n/p,m/p,p)%p);
}
int main(){
    int T;
    scanf("%d",&T);
    for(int o=1;o<=T;o++){
        ll n,m,p;
        scanf("%lld%lld%lld",&n,&m,&p);
        memset(a,0,sizeof(a));
        a[0]=1;
        for(int i=1;i<=100000;i++){
            a[i]=(a[i-1]*i)%p;
        }
        printf("%lld\n",lucas(n+m,n,p));
    }
    return 0;
}

4.中国剩余定理（CRT）：
用来求线性同余方程组，常用作合并答案
具体自己百度，我也没很弄懂，只是背了公式。

//代码未经测试，极有可能出错，仅供参考
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){
        x=1;
        y=0;
        return a;
    }
    ll q=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return q;
}
ll inv(ll a,ll p){
    ll x,y;
    exgcd(a,p,x,y);
    return (x+p)%p;
} 
ll CRT(int n,ll *a,ll *m){
    ll M=1;
    for(int i=1;i<=n;i++){
        M*=m[i];
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        ll t=M/m[i];
        ll x=inv(t,m[i]);
        ans=(ans+a[i]*t*x)%M;
    }
    return (ans+M)%M;
}
int n;
ll a[100001];
ll m[100001];
int main(){

    return 0;
}