首页 > 代码库 > 数论(欧几里得,扩展欧几里得,欧拉)

数论(欧几里得,扩展欧几里得,欧拉)

  今天考试了,三道题分别是求欧拉,逆欧拉,欧拉求和

  对于我这样的蒟蒻来说,我选择狗带。

  爆零稳稳的。

  现在整理一下;

  φ(n)(欧拉函数值)为不大于n的正整数中与n互质的数的个数;

  有几条这样的性质:

    1.欧拉函数是积性函数,但不是完全积性函数,即φ(mn)=φ(n)*φ(m)只在(n,m)=1时成立.

    2.对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn.

    φ(N)=N*(1-1/P1)*(1-1/P2)*...*(1-1/Pn).

    3.除了N=2,φ(N)都是偶数.

    4.设N为正整数,∑φ(d)=N (d|N).

  根据其中第2条性质,我们可以想出求φ(n)的代码

  思路:

    n分解质因数

    代码:

    

#include<cstdio>
#include<iostream>

using namespace std;

long long int n,head=2,ans=1,ans2=1;
bool yinshu[500001000];

int main()
{
    cin>>n;
    long long int cur=n;
    while(head<=n)
    {
        if(cur==1) break;
        if(cur%head==0)
        {
            cur/=head;
            yinshu[head]=true;
        }
        else head++;
    }
    for(int i=2;i<=head;i++)
    {
        if(yinshu[i]==true)
        {
            ans*=i-1;
            ans2*=i;
        }
    }
    ans*=n/ans2;
    cout<<ans<<endl;
    return 0;
}

   当然,其中分解质因数的时候,还可以打一张素数表,但是如果你给的数是大于10^18次方的质数,这个代码无能为力;

  有个算法叫做Miller_Rabin算法,可以很快的判断一个数是不是素数;

   欧几里得算法:

  1.gcd(欧几里得):

  gcd可以用来求最大公约数,直接上代码:

int gcd(int m,int n)
{
    if(n==0) return m;
    else return gcd(n,m%n);
}

  2.扩展欧几里得:

  对于不完全为0的整数a,b存在ax+by==gcd(a,b);

  扩展欧几里得可用于求出x,y;

  根据gcd(欧几里得)可以得出gcd(a,b)==gcd(b,a%b);

  所以

  当b==0时,存在ax+0*y==gcd(a,b)==gcd(a,0)==a;

  所以当b==0时,x==1,y==0;

  同时ax+by==gcd(a,b),bx1+a%by1==gcd(b,a%b);

  所以ax+by==bx1+(a-a/b*b)*y1;

        ax+by==bx1+ay1-a/b*b*y1;

    ax+by==ay1+b(x1-a/b*y1);

    即:

    x==y1,y==x1-a/b*y1;

    由此可得出扩展欧几里得求x,y的递归式,上代码:

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

  接下来是关于扩展欧几里得的一道信息题:

  题目 codevs 1200 同余方程

1200 同余方程

 

2012年NOIP全国联赛提高组

 时间限制: 1 s
 空间限制: 128000 KB
 题目等级 : 钻石 Diamond
 
 
 
题目描述 Description

求关于 x 同余方程 ax ≡ 1 (mod b)的最小正整数解。 

输入描述 Input Description

输入只有一行,包含两个正整数 a, b,用 一个 空格隔开。 

输出描述 Output Description

输出只有一行包含一个正整数x0,即最小正整数解,输入数据保证一定有解。

样例输入 Sample Input

3 10 

样例输出 Sample Output

7

数据范围及提示 Data Size & Hint

【数据范围】
对于 40%  的数据, 2 ≤b≤ 1,000 ;
对于 60% 的数据, 2 ≤b≤ 50,000,000 
对于 100%  的数据, 2 ≤a, b≤ 2,000,000,000

 
  思路:
    题目是求关于x的同余方程ax ≡ 1 (mod b)的最小解
    ax ≡ 1 (mod b),即a*x%b==1;
    原式可简化成ax-ax/b*b==1;
    设-ax/b为y
    则原式成为ax+bx==1 变为可用扩展欧几里得求的数;
    但是求出的x不一定大于等于0
    所以还要有一个小小的转换
    即
int cnm=gcd(a,b);
while(x<0) x+=(b/cnm),y-=(a/cnm);

    然后输出x即可ac;

    上代码:

#include<cstdio>

#define ll long long

using namespace std;

ll int a1,b1,x1,y1;

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

int main()
{
    scanf("%lld%lld",&a1,&b1);
    ll int cnm=exgcd(a1,b1,x1,y1);
    while(x1<0) x1+=(b1/cnm),y1-=(a1/cnm);
    printf("%lld\n",x1);
    return 0;
}

 

数论(欧几里得,扩展欧几里得,欧拉)