数论

Notice:博客对markdown的处理有锅,无法正常显示公式,工程师正在全力解决这个问题。

请前往作业部落备份阅读本文。

所以请不要往下翻了。





















































































































































我就知道还是会有人手贱翻到这里(手动滑稽)。

数论

费马小定理

若p是质数,a是任意整数,并且a不能被p整除,于是:
$a^{p-1}≡1(mod \ p)$

欧拉函数

φ(n)表示1~n以内和n互质的数的个数。
p表示n的所有质因数。
有$φ(n)=n*\prod_{p|n}^p\ (1-\frac{1}{q})$

  • 欧拉函数是积性函数,若m,n互质,则:$φ(mn)=φ(n)*φ(m)$
  • 若n为奇数,则:$φ(2n)=φ(n)$
  • 若n为质数,则:$φ(n)=n-1$

线性筛欧拉函数

int m[maxn],phi[maxn],p[maxn],pt;//m[i]是i的最小素因数,p是素数,pt是素数个数
int get_phi(){
    phi[1]=1;
    int N=maxn,k;
    for(int i=2;i<N;i++){
        if(!m[i]){//i是素数
            p[pt++]=m[i]=i,phi[i]=i-1;
        }
        for(int j=0;j<pt&&(k=p[j]*i)<N;j++){
            m[k]=p[j];
            if(m[i]==p[j]){//为了保证以后的数不被再筛,要break
                phi[k]=phi[i]*p[j];
/*这里的phi[k]与phi[i]后面的∏(p[i]-1)/p[i]都一样(m[i]==p[j])只差一个p[j],就可以保证∏(p[i]-1)/p[i]前面也一样了*/
                break;
            }
            else{
                phi[k]=phi[i]*(p[j]-1);//积性函数性质
            }
        }
    }
}

欧拉定理

若$gcd(a,b)=1$,则:$a^{φ(b)}≡1(mod \ b)$

更常用的:$a^b%m=a^{b%φ(m)+φ(m)}%m$

原根

定义:设m>1,$gcd(a,m)=1$,使得$a^r≡1(mod \ m)$成立的最小的r,称为a对模m的阶,记为$\delta_m(a)$。

数m有原根的充要条件:$m=2,4,p,2p,p^k$ (p为奇素数,k为任意正整数)。

定理

  • 如果模m有原根,那么它一共有$φ(φ(m))$个原根。
  • 若m>1,$gcd(a,m)=1$,$a^n≡1(mod \ m)$,则$\delta_m(a)|n$。
  • 如果p为素数,那么素数p一定存在原根,并且p模的原根的个数为$φ(p-1)$。
  • 设m是正整数,a是整数,若a模m的阶等于$φ(m)$,则称a为模m的一个原根。

找原根

若欲求m的原根的话,对$φ(m)$进行质因数分解,求出所有质因子$p_i$,若对于任意$p_i$,均满足$g^{\frac{φ(m)}{p_i}}\neq 1(mod \ m)$,则g是m的原根。

求原根的代码

#include<bits/stdc++.h>
using namespace std;
int p[100007], c;
long long pow_mod(long long a,long long x,long long m){
    long long ans=1;
    while(x){
        if(x&1){
            ans=ans*a%m;
        }
        a=a*a%m;
        x>>=1;
    }
    return ans;
}
bool ok(int x,int ph,int m){
    for(int i=0;i<c;i++){
        if(pow_mod(x,ph/p[i],m)==1){
            return 0;
        }
    }
    return 1;
}
void divide(int x){
    c=0;
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            p[c++]=i;
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1){
        p[c++]=x;
    }
}
int main(){
    int wxh;
    scanf("%d",&wxh);
    while(wxh--){
        int n;
        scanf("%d",&n);
        int m=n,ans=m;
        for(int i=2;i*i<=n;i++){
            if(n%i==0){
                ans=ans/i*(i-1);
                while(n%i==0){
                    n/=i;
                }
            }
        }
        if(n>1){
            ans=ans/n*(n-1);
        }
        divide(ans);
        int x=ans;
        while(!ok(x,ans,m)){
            x--;
        }
        printf("%d\n",x);
    }
    return 0;
}

二次剩余

当存在某个x,式子$x^{2}≡d(mod\ p)$成立时,称“d是模p的二次剩余”。
当对任意x不成立时,称“d是模p的二次非剩余”。
学不来
关于如何计算二次剩余,详见Miskcoo的博客

解方程a^b≡n(mod p)(p是素数)

一、已知n,p(p是奇数),b=2,求a

由费马小定理:$n^{(p-1)/2}≡\pm1(mod\ p)$
根据欧拉准则,二次剩余有解当且仅当$n^{(p-1)/2}≡1(mod\ p)$
如果c满足$w=c^2-n$不是p的二次剩余,那么$a=(c+\sqrt(w))^{(p-1)/2}$是方程$a^2≡n(mod\ p)$的解。因为有一半的数是非二次剩余,所以可以随机c,验证即可。
详见Philipsweng的博客

二、已知n,p,a,求b

使用Baby-step giant-step算法

发表评论