emm,数论好难,估计要学两周才能全懂。
鉴于目前这里面还是非常的恶心很不全面,就暂时加密吧

emm,先放上手稿吧,当然还没学完,而且还没有理清楚。。。。手稿很乱,大神勿喷。
而且手稿暂时知识存在博客上方便看而已。。。

先一点一点的来吧,数论太杂了,先上凌乱的代码。具体新的以后补上。。。

试除法判断素数

boll isprimes(int n){
    if(n<2)return false;
    for(int i = 2;i<=n/i;i++){
        if(n%i==0)return false;
    }
    return true;
}

分解质因数

void devide(int n){
    for(int i = 2;i<=n/i;i++){
        if(n%i==0){
            int s = 0;
            while(n%i==0)n/=i,s++;
            cout<<i<<" "<<s<<endl;
        }
    }
    if(n!=1)cout<<n<<" "<<1<<endl;
    cout<<endl;
}

筛素数-线性筛

void get_primes(int n){
    for(int i = 2;i<=n;i++){
        if(!st[i])primes[++cnt]=i;
        for(int j = 1;primes[j]<=n/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
    cout<<cnt;
}

试除法求约数

void get_divisors(int x){
    priority_queue<int,vector<int>,greater<int> >;
    for(int i = 1;i<=x/i;i++){
        if(x%i)continue;
        q.push(i);
        if(x/i!=i)q.push(x/i);
    } 
    while(!q.empty()){
        cout<<q.top()<<" ";
        q.pop();
    }
    cout<<endl;
}

求约数个数

void divisors_num(){
    int n,x;
    map<int,int> q;
    cin>>n;
    while(n--){
        cin>>x;
        for(int i = 2;i<=x/i;i++){
            while(x%i!=0){
                x/=i;
                q[i]++;
            }
            if(x>1)q[x]++;
        }
    }
    LL res = 1;
    for(map<int,int>::iterator i=q.begin();i!=q.end();i++){
        res=res*i->second%mod;
    }
    cout<<res<<endl;
}

求约数的和

mapp q;//默认q已经弄完了
LL p(int d,int a){
    LL n;
    while(a--){
        n=(n*d+1)%mod;
    }
    return n;
}
LL ress(){
    LL res=1;
    for(mapp::iterator i = q.begin();i!=q.end();i++){
        res=res*p(i->first,i->second)%mod;
    }
    return res;
}

求最大公约数

int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

求欧拉函数

int phi(int x){
    int res = x;
    for(int i = 2;i<=x/i;i++){
        if(x%i==0){
            res = res /i(i-1);
            while(x%i==0)x/=i;
        }
        if(x>1)res = res /x*(x-1);
    }
    return res;
}

筛法就欧拉函数

ULL res = 1;
int phi[N];
ULL prime[N],cnt;
bool st[N];
ULL get_eulers(int x){
    phi[1]=1;
    for(int i = 2;i<=x;i++){
        if(!st[i]){prime[++cnt]=i;st[i]=true;phi[i]=i-1;res+=phi[i];}
        for(int j = 1;prime[j]<=x/i;j++){
            int t = i*prime[j];
            if(i%prime[j]==0){
                phi[t]=phi[i]*(prime[j]-1);
                res+=phi[t];
                break;
            }
            phi[t]=phi[i]*prime[j];
            res+=phi[t];
        }
    }
    return res;
}

快速幂

int power(int a,int b,int p){
    int res = 1;
    while(b){
        if(b&1)res=(LL)res*a%p;
        a=(LL)a*a%p;
        b>>=1;
    }
    return res;
}

快速幂求逆元(在%prime的情况下)

int power(int a,int b,int p){
    //根据上面的
}
int main(){
    cin>>a>>p;
    if(a%p==0)puts("impossible");
    else cout<<power(a,p-2,p)<<endl;
}

拓展欧几里得算法

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

拓展欧几里得解线性同余方程

int exgcd(int a,int b,int x,int y){
    //同上文
}
int main(){
    cin>>a>>b>>m;
    int d = exgcd(a,b,x,y);
    if(b%d)puts("impossible");
    else cout<<(LL)x*b/d%m<<endl;
}
name.com购买域名廉价稳定无需备案 年付.xyz.site.life$3点击购买赠送5$优惠券
racknerd购买无需备案CN2服务器,速度高速稳定节日优惠力度强 节日会推出各种优惠套餐【点击注册】目前推出3H2.5G40GB6T每年$27.80两年$55.60套餐【快来注册
Last modification:April 11th, 2020 at 12:21 pm
觉得好的话就评论,转发,投币。