Java教程

数学知识(二):欧拉函数、快速幂、扩展欧几里得算法、中国剩余定理

本文主要是介绍数学知识(二):欧拉函数、快速幂、扩展欧几里得算法、中国剩余定理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

欧拉函数

公式法求欧拉函数

基本原理:O(n√ai)

 

 例题:欧拉函数

给定 n个正整数 ai,请你求出每个数的欧拉函数。

欧拉函数的定义

1∼N中与 N 互质的数的个数被称为欧拉函数,记为 ϕ(N)
若在算数基本定理中,N=pa11pa22…pamm,则:
ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm

输入格式

第一行包含整数 n。

接下来 n 行,每行包含一个正整数 ai。

输出格式

输出共 n 行,每行输出一个正整数 ai的欧拉函数。

数据范围

1≤n≤100
1≤ai≤2×109

输入样例:

3
3
6
8

输出样例:

2
2
4

 解题代码:

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    cin >>n;
    
    while(n--)
    {
        int a;
        cin>>a;
        
        int res=a;
        for(int i=2;i<=a/i;i++)//分解质因数
            if(a%i==0)//a是i的质因子
            {
                res=res/i*(i-1);//公式
                while(a%i==0) a/=i;//把i除干净
            }
            
        if(a>1) res=res/a*(a-1);
        
        cout<<res<<endl;
    }
    return 0;
}

筛法求欧拉函数

 

 例题:

给定一个正整数 n,求 1∼n中每个数的欧拉函数之和。

输入格式

共一行,包含一个整数 n。

输出格式

共一行,包含一个整数,表示 1∼n中每个数的欧拉函数之和。

数据范围

1≤n≤106

输入样例:

6

输出样例:

12

 解题代码:

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N=1000010;

int primes[N],cnt;//primes存的是每一个质数,cnt存的是质数的下标
bool st[N];//表示是否被筛掉了
int phi[N];//欧拉函数

LL get_eulers(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)//线性筛法
    {
        if(!st[i])
        {
            primes[cnt++]=i;
            //如果是质数
            phi[i]=i-1;
        }
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;//每次把当前的质数与i的乘积筛掉
            if(i%primes[j]==0)
            {
                phi[primes[j]*i]=primes[j]*phi[i];
                break;
            } 
            
            phi[primes[j]*i]=phi[i]*(primes[j]-1);
        }
    }
    
    LL res=0;
    for(int i=1;i<=n;i++) res+=phi[i];
    return res;
}

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

 欧拉函数作用:

 欧拉定理证明:

 费马定理

 

快速幂 

 

 

 

 例题:快速幂

给定 n 组 ai,bi,pi,对于每组数据,求出 abii mod pi的值。

输入格式

第一行包含整数 n。

接下来 n 行,每行包含三个整数 ai,bi,pi

输出格式

对于每组数据,输出一个结果,表示 abii mod pi的值。

每个结果占一行。

数据范围

1≤n≤100000
1≤ai,bi,pi≤2×109

输入样例:

2
3 2 5
4 3 9

输出样例:

4
1

 解题代码:

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

//求a^b % p
LL qmi(int a, int b, int p)
{
    LL res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * a % p;//%p防止溢出
        a = a * (LL)a % p;
        b >>= 1;//把b的末位删除
    }
    return res;
}


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

    return 0;
}

例题:快速幂求逆元

给定 n 组 ai,pi,其中 pi 是质数,求 ai模 pi 的乘法逆元,若逆元不存在则输出 impossible

注意:请返回在 0∼p−1之间的逆元。

乘法逆元的定义

若整数 b,m互质,并且对于任意的整数 a,如果满足 b|a,则存在一个整数 x,使得 a/b≡a×x(modm)则称 x为 b 的模 m 乘法逆元,记为 b−1(modm)
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时,bm−2 即为 b 的乘法逆元。

输入格式

第一行包含整数 n。

接下来 n 行,每行包含一个数组 ai,pi,数据保证 pi 是质数。

输出格式

输出共 n 行,每组数据输出一个结果,每个结果占一行。

若 ai 模 pi 的乘法逆元存在,则输出一个整数,表示逆元,否则输出 impossible

数据范围

1≤n≤105
1≤ai,pi≤2∗109

输入样例:

3
4 3
8 5
6 3

输出样例:

1
2
impossible

解题思路:

  

解题代码: 

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

//求a^b % p
LL qmi(int a, int b, int p)
{
    LL res = 1 % p;
    while (b)
    {
        if (b & 1) res = res * a % p;//%p防止溢出
        a = a * (LL)a % p;
        b >>= 1;//把b的末位删除
    }
    return res;
}


int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        int a, p;
        scanf("%d%d%", &a, &p);
        
        LL res=qmi(a, p-2, p);
        if(a%p) printf("%lld\n", res);
        else puts("impossible");
    }

    return 0;
}

扩展欧几里得算法

裴蜀定理:

对于任意正整数a,b,一定存在非零整数x,y,使得 :

                ax+by=(a,b)//(a,b)是a、b的最大公约数的倍数

即a,b能凑出的最小的正整数,就是其最大公约数

扩展欧几里得算法就是来求它们的系数的,即x,y

 例题:扩展欧几里得算法

给定 n 对正整数 ai,bi,对于每对数,求出一组 xi,yi使其满足 ai×xi+bi×yi=gcd(ai,bi)

输入格式

第一行包含整数 n。

接下来 n 行,每行包含两个整数 ai,bi

输出格式

输出共 n 行,对于每组 ai,bi求出一组满足条件的 xi,yi每组结果占一行。

本题答案不唯一,输出任意满足条件的 xi,yi 均可。

数据范围

1≤n≤105
1≤ai,bi≤2×109

输入样例:

2
4 6
8 18

输出样例:

-1 1
-2 1

 解题代码:

#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;
}

运用:求解线性同余方程

给定 n 组数据 ai,bi,mi对于每组数求出一个 xi,使其满足 ai×xi≡bi(mod mi)如果无解则输出 impossible

输入格式

第一行包含整数 n。

接下来 n 行,每行包含一组数据 ai,bi,mi

输出格式

输出共 n 行,每组数据输出一个整数表示一个满足条件的 xi,如果无解则输出 impossible

每组数据结果占一行,结果可能不唯一,输出任意一个满足条件的结果均可。

输出答案必须在 int 范围之内。

数据范围

1≤n≤105
1≤ai,bi,mi≤2×109

输入样例:

2
2 3 6
4 3 5

输出样例:

impossible
-3

解题:

 

 

中国剩余定理

 例题:表达整数的奇怪方式

给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn求一个最小的非负整数 x,满足 ∀i∈[1,n],x≡mi(mod ai)

输入格式

第 1 行包含整数 n。

第 2…n+1 行:每 i+1 行包含两个整数 ai 和 mi,数之间用空格隔开。

输出格式

输出最小非负整数 x,如果 x 不存在,则输出 −1。
如果存在 x,则数据保证 x 一定在 64 位整数范围内。

数据范围

1≤ai≤231−1
0≤mi<ai
1≤n≤25

输入样例:

2
8 7
11 9

输出样例:

31

解题:

 

 

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

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

int main()
{
    int n;
    cin >>n;
    
    bool has_answer =true;
    LL a1,m1;
    cin>>a1>>m1;
    
    for(int i=0;i<n-1;i++)
    {
        LL a2,m2;
        cin>>a2>>m2;
        
        //求出k1,k2的值
        LL k1,k2;
        LL d=exgcd(a1,a2,k1,k2);
        //该方程有解
        if((m2-m1)%d)
        {
            has_answer=false;
            break;
        }
        
        //k1,k2 翻倍成m1,m2
        k1*=(m2-m1)/d;
        LL t=a2/d;//先将数存下来
        k1=(k1%t+t)%t;//将k1变成方程的最小正整数解
        
        m1=a1*k1+m1;
        a1=abs(a1/d*a2);
    }
    if(has_answer)
    {
        cout<<(m1%a1+a1)%a1 <<endl;
    }
    else puts("-1");
    
    return 0;
}

 

这篇关于数学知识(二):欧拉函数、快速幂、扩展欧几里得算法、中国剩余定理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!