首页 > 其他分享 >数学知识(一)--质数、约数、欧拉函数、快速幂、扩展欧几里得、高斯消元

数学知识(一)--质数、约数、欧拉函数、快速幂、扩展欧几里得、高斯消元

时间：2025-01-18 16:04:00浏览次数：3  
标签：约数 return int res 质数 -- include 高斯消

目录

一、质数

1.试除法判断质数

2.试除法分解质因数

3.筛选法找质数

(1)朴素筛法--埃氏筛

(2)线性筛法

二、约数 

1.试除法求约数

2.约数个数问题

 3.约数之和问题

4.欧几里得算法(辗转相除法)

三、欧拉函数

1.公式法求欧拉函数

2.线性筛法求欧拉函数 

 3.欧拉定理和费马定理

四、快速幂

 快速幂求逆元

 五、扩展欧几里得算法

 求解线性同余方程

 六、高斯消元

一、质数

1.试除法判断质数

        判定一个数n是否是质数，主要判定2 ~ sqrt(n)之间是否有其约数，并且，所有小于2的数不是质数。

        注意在枚举2-sqrt(n)之间所有数时，不推荐i<=sqrt(n)和i*i<=n这两种写法，原因是每次循环都计算sqrt(n)速度比较慢，而i*i<=n当n去INT_MAX附近时容易造成溢出，死循环。推荐的写法是i<=n/i;

#include<iostream>
#include<cmath>
using namespace std;

bool isPrime(int x){
    if(x<2) return false;
    for(int i=2;i<=x/i;i++){
        if(x%i==0) return false;
    }
    return true;
}

int main(){
    int n;cin>>n;
    while(n--){
        int x;cin>>x;
        if(isPrime(x)) puts("Yes");
        else puts("No");
    }
    return 0;
}

2.试除法分解质因数

#include<iostream>
using namespace std;

void divide(int n){
    for(int i=2;i<=n/i;i++){
        if(n%i==0){//i一定是质数，因为一旦是因数，会把这个因数直到除以干净
            int s=0;
            while(n%i==0){
                n/=i;
                s++;
            }
            printf("%d %d\n",i,s);
        }
    }
    if(n>1) printf("%d %d\n",n,1);//处理大于sqrt(n)的质因数
    puts("");
}

int main(){
    int n;scanf("%d",&n);
    while(n--){
        int x;scanf("%d",&x);
        divide(x);
    }
    return 0;
}

3.筛选法找质数

(1)朴素筛法--埃氏筛

        筛质数的目的在于求出1 ~ n之间的质数。那么比较快速的办法就是将1 ~ n当中不是质数的数给筛出去。

        朴素筛法是利用已经确定了的质数进行筛除，其原理是将一个质数的所有小于等于n的倍数全部筛除。

#include<iostream>
using namespace std;

const int N=1000010;
int primes[N],cnt;
bool st[N];

void get_primes(int n){
    for(int i=2;i<=n;i++){
        if(st[i]) continue;//该数被筛掉，跳过该循环
        primes[cnt++]=i;//加入素数表
        for(int j=i+i;j<=n;j+=i) st[j]=true;//删去该素数的倍数
    }
}

int main(){
    int n;cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    return 0;
}

(2)线性筛法

        当数据在10^6时，线性筛法和埃氏筛法速度差不多，10^7时线性筛法比埃氏筛法快一倍。

#include<iostream>
using namespace std;

const int N=1000010;
int primes[N],cnt;
bool st[N];

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

int main(){
    int n;cin>>n;
    get_primes(n);
    cout<<cnt<<endl;
    return 0;
}

二、约数 

1.试除法求约数

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

vector<int> get_divisors(int n){
    vector<int> res;
    for(int i=1;i<=n/i;i++){
        if(n%i==0){
            res.push_back(i);
            if(i!=n/i) res.push_back(n/i);
        }
    }
    sort(res.begin(),res.end());
    return res;
}

int main(){
    int n;cin>>n;
    while(n--){
        int x;cin>>x;
        auto res=get_divisors(x);
        for(auto t:res) cout<<t<<" ";
        puts("");
    }
    return 0;
}

2.约数个数问题

int范围内的数的约数个数最多是1500个左右。

该算法求解的是一个数x的所有2 ~ x - 1中的约数个数

该算法基于约数个数公式(a₁ + 1) * (a₂ + 1) * … * (ak + 1)，其中a1为x的第一个质因子的指数，a₂为x的第二个质因子的指数，依次类推。

#include<iostream>
#include<unordered_map>
using namespace std;
const int N=1e9+7;

int main(){
    int n;cin>>n;
    unordered_map<int,int> primes;
    while(n--){
        int x;cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1) primes[x]++;
    }
    long long res=1;
    for(auto prime:primes) res=res*(prime.second+1)%N;
    cout<<res<<endl;
    return 0;
}

 3.约数之和问题

 该算法同样基于公式，(p1^0 + p1^1 + … + p1^a1) * … * (pk^0 + pk^1 + … + pk^ak)。其中，p1是第一个质因子，a1是第一个质因子的指数。
上式中，可以利用t = t * p + 1求解每一项，例如：t1 = 1，t1 = p + 1，t2 = p^2 + p + 1，…,ta = p^a1 + …… + 1

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

const int N=1e9+7;

int main(){
    int n;cin>>n;
    unordered_map<int,int> primes;
    while(n--){
        int x;cin>>x;
        for(int i=2;i<=x/i;i++){
            while(x%i==0){
                x/=i;
                primes[i]++;
            }
        }
        if(x>1) primes[x]++;
    }
    long long res=1;
    for(auto prime:primes){
        int p=prime.first,a=prime.second;
        long long t=1;
        while(a--) t=(t*p+1)%N;
        res=res*t%N;
    }
    cout<<res<<endl;
    return 0;
}

4.欧几里得算法(辗转相除法)

        如果一个数d能整除a，且能整除b，那么d一定能整除c1 * a + c2 * b。所以d也能够整除a - c * b，令c = (a / b)向下取整，则a - c * b = a mod b，所以d也能整除a mod b，故a, b两个数的最大公约数等于b, a mod b这两个数的最大公约数。这就是欧几里得算法的核心之处。

#include<iostream>
using namespace std;

int gcd(int a,int b){
    // int c;
    // while(b){
    //     c=a%b;
    //     a=b;
    //     b=c;
    // }
    // return a;
    return b?gcd(b,a%b):a;
}

int main(){
    int n;cin>>n;
    while(n--){
        int a,b;cin>>a>>b;
        cout<<gcd(a,b)<<endl;
    }
    return 0;
}

三、欧拉函数

1.公式法求欧拉函数

首先看互质的定义：

#include<iostream>
using namespace std;

int main(){
    int n;scanf("%d",&n);
    while(n--){
        int x;scanf("%d",&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);
        printf("%d\n",res);
    }
    return 0;
}

2.线性筛法求欧拉函数 

a.一个质数n的欧拉函数为值为n-1。

b.当i%pj==0时，pj是i的一个质因子，所以pj*i的分解质因数的质因数相同，只是pj那一项的次数多1。所以可推导pj*i的欧拉函数值为i的欧拉函数值*pj。

c.当i%pj！=0时，pj不是i的质因子，但也是pj*i的最小质因子。因此在pj*i的欧拉减函数中，只是比i多了一个质因子pj和系数pj。而pj*（1-1-pj）=（pj-1）//质数的欧拉函数公式。=>(pj-1)*phi(i)

d.别忘了1的欧拉函数值为1（1和自己互质）。

#include<iostream>
using namespace std;

const int N = 1000010;

typedef long long ll;
int primes[N], cnt;
int phi[N];
bool st[N];

ll get_eulers(int n) {
    ll ans = 1;
    for (int i = 2;i <= n;i++) {
        if (!st[i]) {//当i为质数时
            primes[cnt++] = i;
            phi[i] = i - 1;
            ans += phi[i];
        }
        for (int j = 0;primes[j] <= n / i;j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) {//当pj为i的最小质因子时
                phi[primes[j] * i] = primes[j] * phi[i];
                ans += phi[primes[j] * i];
                break;
            }
            //当pj不是i因子，但是pj*i的最小质因子时
            phi[primes[j] * i] = (primes[j] - 1) * phi[i];
            ans += phi[primes[j] * i];
        }
    }
    return ans;
}

int main() {
    int n;scanf("%d", &n);
    printf("%ld\n", get_eulers(n));
    return 0;
}

 3.欧拉定理和费马定理

欧拉定理：

费马定理： 

 特别地，当n为质数p时：

四、快速幂

朴素做法O(n)

 快速幂O(log n)

        快速幂可以快速求解a^b % p的结果。a^b在java中虽然有方法pow可以使用，但是在计算过程中很容易就爆long，而快速幂计算的每一步都mod p，一般就不会爆long。

        其思想为先预处理出a^(2^0), a^(2^1),… , a^(2^log(k))的结果，这些数每一个都是前一个的平方。这一步显然是log(b)复杂度的。

        再将a^b分解为若干个前面预处理出来的值相乘，即将b分解为前面预处理出来的值的指数相加，这一步可以使用二进制进行计算，例如：十进制中的a^5，5的二进制的101，则5可以写为2^0 + 2^2 ，那么a^5就被分解为a^(2^0) * a^(2^2)，此时就可以用预处理出来的值相乘得到。而这一步显然也是log(b)的，因此时间复杂度为log(b)。

#include<iostream>
using namespace std;

typedef long long ll;

//a^k%p
int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(ll)res*a%p;
        k>>=1; //每次右移一位
        a=(ll)a*a%p;
    }
    return res;
}

int main(){
    int n;scanf("%d",&n);
    while(n--){
        int a,k,p;
        scanf("%d%d%d",&a,&k,&p);
        printf("%d\n",qmi(a,k,p));
    }
    return 0;
}

 快速幂求逆元

当p是质数时，b模p的乘法逆元为b^(p-2)

根据费马定理：

 

#include<iostream>
using namespace std;

typedef long long ll;

int qmi(int a,int k,int p){
    int res=1;
    while(k){
        if(k&1) res=(ll)res*a%p;
        k>>=1;
        a=(ll)a*a%p;
    }
    return res;
}

int main(){
    int n;scanf("%d",&n);
    while(n--){
        int a,p;scanf("%d%d",&a,&p);
        //有逆元的充要条件是a、p互质
        //因为p是质数，所以a、p互质的话<=>a不是p的倍数
        if(a%p==0) puts("impossible");
        else printf("%d\n",qmi(a,p-2,p));
    }
    return 0;
}

 五、扩展欧几里得算法

        想了解扩展欧几里得算法，先引入**裴属定理：**若 a, b 是整数,且 gcd(a , b) = d ，那么对于任意的整数x, y , ax + by都一定是d的倍数，特别地，一定存在整数 x, y，使ax + by = d成立。而扩展欧几里得算法则可以很方便的求解任意正整数a, b的x, y这两个系数。即通过函数exgcd(a, b, x, y)求得系数x, y。值得注意：x, y并不唯一。

        由欧几里得算法知，gcd(a, b) = gcd(b, a % b)，而a % b = a - a / b * b ，那么在递归求gcd（b, a % b, y, x)时有by + (a % b)x = d，化简得ax + (y - a / b * x)b = d，说明在递归时系数x不用更新（这里的x是指exgcd函数里的x，因为在每次进行递归时，会将实参交换后再复制给形参），只需要更新y。

#include<iostream>
using namespace std;

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 main(){
    int n;scanf("%d",&n);
    while(n--){
        int a,b,x,y;scanf("%d%d",&a,&b);
        exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}

解不唯一：（拓展）求所有解：

 求解线性同余方程

        可以通过扩展欧几里得算法求解线性同余方程ax ≡ b (mod m)。从取模的定义出发，可以根据ax ≡ b (mod m)构造出ax = my' + b，令y = -y'，整理得ax + my = b，当b为a, m的最小公倍数的倍数时，可以利用扩展欧几里得算法进行求解，而当b不是其倍数时，则无解。

        当用扩展欧几里得求出一组x0, y0后，此时的x0, y0满足的是ax0 + my0 = gcd(a, m)，此时，我们将等式两边同时乘以b / gcd(a, m)，得到ax0(b / gcd(a, m)) + my0(b / gcd(a, m)) = b，令x = x0(b / gcd(a, m))，y = y0(b / gcd(a, m))，则此时的x, y即为原线性同余方程的一组解。

#include<iostream>
using namespace std;

typedef long long ll;

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 main(){
    int n;scanf("%d",&n);
    while(n--){
        int a,b,m;scanf("%d%d%d",&a,&b,&m);
        int x,y;
        int d=exgcd(a,-m,x,y);
        if(b%d) puts("impossible");
        else printf("%d\n",(ll)x*(b/d)%m);
    }
    return 0;
}

 六、高斯消元

        模拟线性代数求解：

 

#include<iostream>
#include<cmath>
using namespace std;

const int N=110;
const double eps=1e-6;
int n;
double a[N][N];

int gauss(){
    int c,r;
    for(c=0,r=0;c<n;c++){
        int t=r;//t记录当前列绝对值最大的那一行
        for(int i=r;i<n;i++){
            if(fabs(a[i][c])>fabs(a[t][c])) t=i;
        }
        if(fabs(a[t][c])<eps) continue;//主元为0时,继续下一列
        
        for(int i=c;i<=n;i++) swap(a[t][i],a[r][i]);// 将绝对值最大的行交换到当前行的上面
        for(int i=n;i>=c;i--) a[r][i]/=a[r][c]; // 将当前行的主元变为 1，从后往前处理，避免数据被提前覆盖
        // 对当前行下面的行进行消元操作
        for(int i=r+1;i<n;i++){
            if(fabs(a[i][c])>eps){// 如果当前行的当前列元素不为 0，则进行消元操作
                for(int j=n;j>=c;j--)
                    a[i][j]-=a[r][j]*a[i][c];
            }
        }
        r++;
    }
    if(r<n){
        for(int i=r;i<n;i++){ // 检查是否无解，如果某行的最后一个元素不为 0 但主元为 0，则无解
            if(fabs(a[i][n])>eps) return 2;//无解
        }
        return 1;//无穷多组解
    }
    //唯一解
    for(int i=n-1;i>=0;i--){
        for(int j=i+1;j<n;j++){
            a[i][n]-=a[i][j]*a[j][n];// 回代求解，消除未知数
        }
    }
    return 0;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n+1;j++)
            cin>>a[i][j];
    int t=gauss();
    if(t==0){
        for(int i=0;i<n;i++) printf("%.2lf\n",a[i][n]);
    }else if(t==1) puts("Infinite group solutions");
    else puts("No solution");
    return 0;
}

 

 

 

 

 

标签：约数,return,int,res,质数,--,include,高斯消
From： https://blog.csdn.net/a2946501058/article/details/145210031

相关文章

  • 高斯消元与高斯-约旦消元
    题目1洛谷P3389【模板】高斯消元法总的来说，就是求解一个nnn元一次方程组。高斯消元思路：首先把所有系数看成一个矩阵：......
  • 01.求200万以内的质数
    一、题目思路1、设两个整数a和b，如果不是质数的话，整数x就可以写成x=a*b比如：36=2*1836=4*936=6*6        如果整数x为质数，就不可能写成x =a*b的形式，即如果不为质数，其中一个可整除的因数一定满足小于等于根号x，缩短遍历判断范围，即判断到根号x是......
  • 【入门】求两个自然数M和N的最大公约数
    题目描述求两个自然数M和N的最大公约数(M，N<=1000）最大公约数，也称最大公因数、最大公因子，指两个或多个整数共有约数（因子）中最大的一个。输入格式输入一行，包括两个整数M,N。输出格式输出只有一行（这意味着末尾有一个回车符号），包括1个整数。输入数据14560输出数据......
  • 应用质数和模算法
    生成RSA加密密钥密钥生成时先选择两个素数p和q，计算他们的乘积n=p*q，RSA的安全性是基于从n推导出p和q是很困难的，p和q越大，在给定n推到p和q的值越难，简单逻辑如下：1、选择两个大的素数2、计算n和phi（欧拉商函数）3、选择一个公共指数e4、计算私有指数d5、使用公钥加密信息6、使用私......
  • 斐波那契与公约数
    斐波那契与公约数设斐波那契数列第\(i\)项为\(f_i\)。\[f_i=\begin{cases}1&(i\leq2)\\f_{i-1}+f_{i-2}&(i>2)\end{cases}\]Lemma1\[\gcd(f_i,f_{i+1})=1\]Proof1数学归纳法。当\(i=1\)时，\(\gcd(f_1,f_2)=\gcd(1,1)=1\)。设\(f_k=a,f_{k+1}=b\)，则有\......
  • 7-403 互质数
    Sg认识到互质数很有用。若两个正整数的最大公约数为1，则它们是互质数。要求编写函数判断两个整数是否互质数。输入格式:首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试先输入1个整数n(1≤n≤100)，再输入n行，每行有一对整数a、b(0<a，b<109)。输出格式......
  • LeetCode 762[二进制表示中质数个计算置位]
    题目链接LeetCode762[二进制表示中质数个计算置位]详情实例提示题解思路两个条件：1、二进制位为12、满足条件1的个数为质数  首先for循环遍历区间for(inti=left;i<right+1;i++){intiCount=0;//二进制位为1的个数......
  • 2025-01-01：优质数对的总数Ⅰ。用go语言，给定两个整数数组 nums1 和 nums2，分别长度为 n
    2025-01-01：优质数对的总数Ⅰ。用go语言，给定两个整数数组nums1和nums2，分别长度为n和m，以及一个正整数k。如果nums1数组中的元素nums1[i]能被nums2数组中的元素nums2[j]乘以k除尽，则称(i,j)为一个优质数对（其中0<=i<=n-1，0<=j<=m-1）。请计算并返回所......
  • 【C++】B2085 第 n 小的质数
    博客主页：[小ᶻ☡꙳ᵃⁱᵍᶜ꙳]本文专栏:C++文章目录......
  • P1306 斐波那契公约数
    P1306斐波那契公约数对于Fibonacci数列：\[f_i=\begin{cases}[i=1]&i\leq1\\f_{i-1}+f_{i-2}&i\gt1\end{cases}\]请求出\(f_n\)与\(f_m\)的最大公约数，即\(\gcd(f_n,f_m)\)。数据规模与约定对于\(100\%\)的数据，保证\(1\l......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99