数论——欧几里得与模线性方程

欧几里得定理

    对任意的非负整数a和和任意正整数b，有gcd(a, b) = gcd(b, a%b)

    这个定理可以用来求a和b的最大公约数，假设a>b，时间复杂度为O(logb)。

扩展欧几里得

    它是欧几里得算法的推广，使它能计算出满足下列条件的整数系数x和y：

ax + by = gcd(a, b)

    注意，x和y可能为0或负数，用它来计算模乘法的逆元也很有效。

    根据gcd(a,b)=gcd(b,a%b)

                                              ax + by = d                                        (1)

    bx' + (a%b)y' = d  -->  bx' + (a-a/b*b)y' =  d -->

                               ay' + b(x' - a/b*y') = d                                     (2)

    若求出x'和y'，比较式(1)和式(2)的系数，有：

x = y',  y = x' - a/b*y'

    扩展欧几里得与欧几里得运行时间相同，两者相差不超过一个常数因子。

typedef __int64 int64;
/**
功能：已知a,b，求解ax+by = gcd(a,b)
输入参数：a和b
输出参数：返回gcd(a,b)，x，y。
*/
int64 Extend_Euclid(int64 a, int64 b, int64& x, int64& y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int64 d = Extend_Euclid(b,a%b,x,y);
    int64 t = x;
    x = y;
    y = t - a/b*y;
    return d;
}

求解模线性方程

    考虑求解下列方程：

ax = b (mod n)

    设<a>表示由a生成的Zn的子群。由于<a>={ax mod n, x>0}，所有方程有一个解b当且仅当b属于<a>。

定理：

  对任意正整数a和n，如果d=gcd(a,n)，则在Zn中

<a> = <d> = {0,d,2d,...,((n/d)-1)d}

因此有|<a>| = n/d。

 

    方程ax=b(mod n)对于未知量x有解，当且仅当gcd(a,b)|b。它或者误解，或者有d个解，周期为n/d。

将方程改写为ax + ny = b。可以先求ax'+ny'=gcd(a,n)=d的一组解x'y'，则x'b/gcd(a,b)是原方程的一个解，令它为x0。

解集可以写为：

xi = x0 + (n/d)*i

证明：

axi mod n = a(x0+(n/d)*i) mod n = (ax0 + ina/d) mod n = ax0 mod n (因为d|a) = b

所以方程有d个不同的解。

/**
功能：求解模线性方程ax=b(mod n)
输入参数：a,b,n
返回参数：模线性方程解的最小值，无解返回-1
*/
int64 Modular_Linear_Equation(int64 a, int64 b, int64 n)
{
    int64 x,y;
    int64 d = Extend_Euclid(a,n,x,y);
    if(b%d)
        return -1;
    int64 x0 = x*(b/d);
    x0 = (x0%n+n)%n;
    return x0%(n/d);    //d个解,相差n/d (模n/d同余)
}

例：POJ1061 2115

 

 附POJ1061代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef __int64 int64;

int64 Extend_Euclid(int64 a, int64 b, int64& x, int64& y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int64 d = Extend_Euclid(b,a%b,x,y);
    int64 t = x;
    x = y;
    y = t - a/b*y;
    return d;
}

int64 Mod_Linear_Equation(int64 a, int64 b, int64 n)
{
    int64 x1,y1,gcd;
    gcd = Extend_Euclid(a,n,x1,y1);
    if(b%gcd)
        return -1;
    //解集共d个解，周期为n/d，xi=x1+(n/d)*i(mod n)
    return (x1*b/gcd%n + n)%n%(n/gcd);
}

int main()
{
    int64 m,n,x,y,L;
    int64 a,b,N;
    while(scanf("%I64d %I64d %I64d %I64d %I64d",&x,&y,&m,&n,&L)!=EOF)
    {
        a = m - n;
        b = y - x;
        N = L;
        if(a==0)
        {
            printf("0\n");
            continue;
        }
        if(a < 0)
        {
            a = -a;
            b = -b;
        }
        if(b < 0)
            b = (b%N+N)%N;
        int64 result = Mod_Linear_Equation(a,b,N);
        if(result == -1)
            printf("Impossible\n");
        else
            printf("%I64d\n",result);
    }
    return 0;
}