调用火速幂算出a^(p-2)就能够,数论尾数

1.扩展gcd

欧几里得算法:
递归版本:

数论尾数,又称逆元(因为自个儿说习惯逆元了,上边笔者都说逆元)

ax≡壹(mod m) , ax+my=壹, 调用一次增添gcd就能够求出x。

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

数论中的尾数是有专门的意义滴

二.费马小定理

迭代版本:

您感到a的倒数在数论中还是1/a啊

如果gcd(a,p)= 1, 那么a^(p-1) ≡ 1(mod p)

int gcd(int a,int b)
{
    while(b!=0)
    {
        int r=b;
        b=a%b;
        a=r;
    }
    return a;
}

(・∀・)哼哼~天真

也就是a^(p-2)*a ≡ 一(mod)p,
a^(p-贰)便是a的逆元,调用快捷幂算出a^(p-2)就能够

恢宏欧几Reade算法:
骨干算法:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b
的最大公约数,必然存在整数对 x,y ,使得 gcd(a,b)=ax+by。

 

三.欧拉定理

证明:设 a>b。
  1,显然当 b=0,gcd(a,b)=a。此时 x=1,y=0;
  2,ab!=0 时
  设 ax1+by1=gcd(a,b);
  bx2+(a mod b)y2=gcd(b,a mod b);
  依照朴素的欧几Reade原理有 gcd(a,b)=gcd(b,a mod b);
  则:ax1+by1=bx2+(a mod b)y2;
  即:ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)*by2;
  根据恒等定理得:x1=y2; y1=x贰-(a/b)y二;
如此那般大家就获得了求解 x一,y一 的艺术:x1,y一 的值基于 x二,y二.

先来引进求余概念

f(x):[1-x-1]内与x互素的数的个数, a^f(p) ≡ 1(mod p)
(依然供给a,p互素), a的逆元为a^(f(p)-1)

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

 

4.线性递推

扩展欧几里德算法的行使首要有以下三地方:
(一)求解不定方程;
(2)求解模线性方程(线性同余方程);
(三)求解模的逆元;

(a +  b) % p =
(a%p +  b%p) %p  (对)

求1-x对p的逆元。一的逆元是一, 对于i, 设p = ki+r (r<i), 分明ki+r ≡
0(mod p).两边同乘i^-1 * r^-1

(一)使用扩展欧几Reade算法消除不定方程的办法:
对此不定整数方程a*x+b*y=c,若 c mod Gcd(x,
y)=0,则该方程存在整数解,不然不设有整数解。
下边已经列出找2个整数解的法子,在找到 a*x+ b*y =
Gcd(a,b)的1组解x0,y0后,
a*x+b*y = Gcd(a, b)的任何整数解满足:
x = x0 + b/Gcd(a, b) * t
y = y0 – a/Gcd(a, b) * t(当中t为任意整数)
因为a*x+b*y=a(x0 + b/Gcd(a, b) * t)+b(y0 – a/Gcd(a, b) * t)=Gcd(a,b)

(a  –  b) % p =
(a%p  –  b%p) %p  (对)

kr^-1 + i^-1 ≡ 0(mod p), i^-1 = -k*r^-1, i^-1 ≡ -(p/i)*(p%i)^-1 (mod
p)

内部,最小的正整数x为: x=x0%( b/Gcd(a, b) )
细微的正整数y: y=y0%( a/Gcd(a, b) )

(a  *  b) % p =
(a%p *  b%p) %p  (对)

void inverse(){
    memset(inv,0,sizeof(inv));
    inv[1]=1;
    for (int i = 2;i <= maxn; i++){
        inv[i] = inv[mod%i]*(mod-mod/i)%mod;
    }
}

至于ax+by=c的平头解,只需将a*x+b*y= Gcd(a,b)的各种解乘上 c/Gcd(a,b)
就可以。

(a  /  b) % p =
(a%p  /  b%p) %p  (错)

 

用扩充欧几里得算法解不定方程ax+by=c;

 

心痛明天组成代表队赛时一种方法也不会

bool linear_equation(int a,int b,int c,int &x,int &y)
{
    int d=exgcd(a,b,x,y);
    if(c%d)
        return false;
    int k=c/d;
    x*=k; y*=k;    //初解
  /*
  x=x+b/(gcd(a,b))*t;//其他解
  y=y-a/(gcd(a,b))*t;
  t为任意整数
  */
    return true;
}

为什么除法错的

 

(二)用扩大欧几Reade算法求解模线性方程的不2诀要:
同余方程 ax≡b (mod n),即(a*x-b) mod
n=0;推出a*x+n*y=b;所以转化为求不定方程a*x+n*y=Gcd(a,n)。
如果b%(Gcd(a,n))!=0,那么方程无整数解;不然求出初解x0,然则初值还要乘以b/Gcd(a,n),即x=x0*b/Gcd(a,n)才是方程a*x+n*y=b的解
而别的整数解则满意:
x(i) = x + b/Gcd(a, b) * t
y(i) = y – a/Gcd(a, b) * t (个中t为任意整数)

申明是对的难,注明错的比方举三个反例      

bool modular_linear_equation(int a,int b,int n)
{
    int x,y,x0,i;
    int d=exgcd(a,n,x,y);
    if(b%d)
        return false;
    x0=x*(b/d)%n;   //特解
    for(i=1;i<d;i++)
        printf("%d\n",(x0+i*(n/d))%n);
    return true;
}

(100/50)%20 = 2  
    ≠      (100%20) / (50%20) %20 = 0

(三)用欧几Reade算法求模的逆元:
乘法逆元:假设a*x≡一 (mod
p),且gcd(a,p)=1(a与p互质),则称a关于模p的乘法逆元为x。
它的同余方程ax+py=gcd(a,p)=一,而一%一==0,所以肯定有解

 

LL exgcd(LL a,ll b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    ll gcd=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return gcd;
}
LL reverseMod(LL a,LL mod)
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);//求初解x
    //其他解为x(i) = x+b/Gcd(a, b)*t=x+mod/1*t=x+mod*t
    while(x<0) x+=mod;//求出一个x>0的逆元
    return x;

} 

对此有个别难点,大家不可能不在中间进程中进行求余,不然数字太大,计算机存不下,那假使这一个算式中出现除法,大家是或不是对那么些算式就不只怕测算了吧?

( 四 )用费马小定理求乘法逆元。
由费马小定理a^(p-一)≡ 一(mod p)(p为素数),稍作变形就是 a*a^(p-贰)≡ 一(mod
p),是或不是发现了,a^(p-二)正是a的逆元,那几个能够用异常快幂来求。

答案自然是
NO (>o<)

typedef long long LL;
LL fast_multi(LL a,LL b,LL mod)
{
    LL res=0,base=a;
    while(b)
    {
        if(b&1) res=(res+base)%mod;
        b>>=1;
        base=(base+base)%mod;
    }
    return res;
}
LL pow_mod(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1) res=fast_multi(res,base,mod);
        base=fast_multi(base,base,mod);
        b>>=1;
    }
    return res;
}//b关于对mod取模的逆元为pow_mod(b,mod-2,mod);

 

题目:求(a/b)%mod。
题解:先求出b的逆元,然后结果为(a*(b^-一)
)%mod,b^-壹指b关于对mod取模运算的逆元

此时就需求逆元了

#include<stdio.h>
#include <string.h>
using namespace std;
const long long mod=9973;//一个素数
typedef long long LL;
LL fast_multi(LL a,LL b,LL mod)
{
    LL res=0,base=a;
    while(b)
    {
        if(b&1) res=(res+base)%mod;
        b>>=1;
        base=(base+base)%mod;
    }
    return res;
}
LL pow_mod(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1) res=fast_multi(res,base,mod);
        base=fast_multi(base,base,mod);
        b>>=1;
    }
    return res;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    LL gcd=exgcd(b,a%b,x,y);
    LL temp=x;
    x=y;
    y=temp-a/b*y;
    return gcd;
}
LL reverseMod(LL a,LL mod)
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);
    while(x<0) x+=mod;
    return x;

}
int main()
{
    int n;
    LL a,b,x;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lld%lld",&a,&b);
        x=reverseMod(b,mod);
        printf("%lld\n",fast_multi(a,x,mod));//扩展欧里几德
        printf("%lld\n",fast_multi(a,pow_mod(b,mod-2,mod),mod));//费马小定理
    }
}

 

大家通晓

如果

a*x = 1

那么x是a的倒数,x
= 1/a

然而a倘诺不是一,那么x正是小数

那数论中,一大半情形都有求余,所现在后主题素材变了

a*x  = 1 (mod
p)

那么x一定等于1/a吗

不一定

由此那时,大家就把x看成a的尾数,只可是加了二个求余条件,所以x叫做
   a关于p的逆元

 

比如2 * 3 % 伍 =
一,那么3正是二关于伍的逆元,或然说二和叁有关伍互为逆元

那边三的职能是或不是跟1/2的职能同样,所以才叫数论最后多少个

 

b的逆元,我们用inv(b)来表示

 

那么(a  /  b) % p
= (a * inv(b) ) % p = (a % p * inv(b) % p) % p

如此这般就把除法,完全调换为乘法了 (。・ω・),乘法超轻巧

 

 

 

正篇起头

 

逆元怎么求

(忘了说,a和p互质,a才有关于p的逆元)

 

方法一:

费马曾经说过:不想当地医学家的科学家不是好科学家(( ̄▽ ̄)~*自个儿随便说的,别当真)

费马小定理

a^(p-1) ≡1 (mod
p)

两边同除以a

a^(p-2) ≡1/a (mod
p)

怎么(,,• ₃
•,,),那然而数论,还敢写1/a

应该写a^(p-2) ≡
inv(a) (mod p)

 

所以inv(a) =
a^(p-2) (mod p)

其一用便捷幂求一下,复杂度O(logn)(ง
•̀_•́)ง 

 

 1 LL pow_mod(LL a, LL b, LL p){//a的b次方求余p 
 2     LL ret = 1;
 3     while(b){
 4         if(b & 1) ret = (ret * a) % p;
 5         a = (a * a) % p;
 6         b >>= 1;
 7     }
 8     return ret;
 9 }
10 LL Fermat(LL a, LL p){//费马求a关于b的逆元 
11         return pow_mod(a, p-2, p);
12 }

 

方法二:

 

要用扩张欧几Reade算法

还记得扩展欧几Reade吗?(不记得的话,欧几里得会不好过的(╭ ̄3 ̄)╭♡)

 

a*x + b*y =
1

如果ab互质,有解

 

其1解的x正是a关于b的逆元

y就是b关于a的逆元

缘何吧?

 

您看,两边同时求余b

 

a*x % b + b*y %
b = 1 % b

a*x % b = 1 %
b

a*x = 1 (mod
b)

 

您看您看,出现了!!!(/≥▽≤/)

所以x是a关于b的逆元

反之可注明y

 

附上代码:

 

 1 #include<cstdio>
 2 typedef long long LL;
 3 void ex_gcd(LL a, LL b, LL &x, LL &y, LL &d){
 4     if (!b) {d = a, x = 1, y = 0;}
 5     else{
 6         ex_gcd(b, a % b, y, x, d);
 7         y -= x * (a / b);
 8     }
 9 }
10 LL inv(LL t, LL p){//如果不存在,返回-1 
11     LL d, x, y;
12     ex_gcd(t, p, x, y, d);
13     return d == 1 ? (x % p + p) % p : -1;
14 }
15 int main(){
16     LL a, p;
17     while(~scanf("%lld%lld", &a, &p)){
18         printf("%lld\n", inv(a, p));
19     }
20 }

 

 

 

方法三:

当p是个质数的时候有
inv(a) = (p – p /
a) * inv(p % a) % p

那怎么是对的咩?

证实不想看的儿女能够跳过。。。( ̄0
 ̄)

证明:
设x = p % a,y = p
/ a
于是有 x + y * a
= p
(x + y * a) % p
= 0
移项得 x % p =
(-y) * a % p
x * inv(a) % p =
(-y) % p
inv(a) = (p – y)
* inv(x) % p
于是 inv(a) = (p

  • p / a) * inv(p % a) % p

下一场直接递归到一结束,因为壹的逆元正是一

 

代码:

 1 #include<cstdio>
 2 typedef long long LL;
 3 LL inv(LL t, LL p) {//求t关于p的逆元,注意:t要小于p,最好传参前先把t%p一下 
 4     return t == 1 ? 1 : (p - p / t) * inv(p % t, p) % p;
 5 }
 6 int main(){
 7     LL a, p;
 8     while(~scanf("%lld%lld", &a, &p)){
 9         printf("%lld\n", inv(a%p, p));
10     }
11 }

 

本条点子不限于求单个逆元,比前五个好,它能够在O(n)的复杂度内算出n个数的逆元

递归就是上边的写法,加3个回想性递归,就足以了

递推这么写

 

 1 #include<cstdio>
 2 const int N = 200000 + 5;
 3 const int MOD = (int)1e9 + 7;
 4 int inv[N];
 5 int init(){
 6     inv[1] = 1;
 7     for(int i = 2; i < N; i ++){
 8         inv[i] = (MOD - MOD / i) * 1ll * inv[MOD % i] % MOD;
 9     }
10 }
11 int main(){
12     init();
13 }

 

又学到新知识了o(*≧▽≦)ツ好开心

 

张开欧几里得(Extend- Euclid)

 

背景:

 

扩大欧几Reade算法是用来在已知a, b求解1组x,y
[x,y都以整数],使它们满意贝祖等式: ax+by = gcd(a, b)
=d(解一定期存款在,依照数论中的相关定理)。增加欧几Reade常用在求解模线性方程及方程组中。
                                                                       
                                                                       
                                                                   
 ——百度完善

 

用到的多少个欧几里得主要结论:

 

1)            gcd(a,b) =  gcd(b,a %b);

 

2)            gcd(a,0) =  a.

代码:

 (1)

 1 ll exgcd(ll a, ll b, ll &x, ll &y)
 2 {
 3     ll d;
 4     //if (a == 0 && b == 0) return -1;// 无GCD
 5     if (b == 0)
 6     {
 7         x = 1;
 8         y = 0;
 9         return a;
10     }
11     d = exgcd(b, a%b, y, x);
12     y -= a / b * x;
13     return d;
14 }
15 
16 //求a关于模n的逆元,不存在返回-1
17 ll inverse(ll a, ll MOD)
18 {
19     ll x, y, d;
20     d = exgcd(a, MOD, x, y);
21     if (d == 1)
22         return (x % MOD + MOD) % MOD;
23 
24    // else   return -1;
25 }

(2)

 1 typedef __int64 ll;
 2 void exgcd(ll a, ll b, ll& d, ll& x, ll &y)
 3 {
 4     if(!b)
 5     {
 6         d = a, x = 1, y = 0;
 7     }
 8     else
 9     {
10         exgcd(b, a % b, d, y, x);
11         y -= x * (a / b);
12     }
13 }

 

 

 

 

分析:

 

设如下七个方程:

 

ax+by  =  gcd(a,b)  =  d;

 

bx’+(a%b)y’  =  gcd(b,a%b);

 

那就是说由重要结论(一)有gcd(a,b)  =  gcd(b,a %b),

 

那么ax+by  =  bx’+(a%b)y’  =  bx’ +(a – [a/b]*b)y’  =  ay’ + b(x’ –
[a/b]y’),

 

由恒等关系有: x = y’ , y = (x’ –
[a/b]y’)
,[a/b]意味着a/b的值向下取整。

 

那就是说未来就可以用exgcd(a,b,d,x,y)表示方程ax+by =
d,那么由地点一直递归下去,直到 b = 0,递归停止,此时  d = gcd(a,0) =a ,
x = 一,y =0;【因为 ax+0*y = gcd(a,0)嘛~】

 

举行欧几里得的多少个使用

 

求解不定方程

 

诸如:求解不定整数方程ax+by = c

 

求ax+by = c, 令d =gcd(a,b);

 

那么(a / d ) * x + (b / d )* y = c / d

 

因为(a / d )、(b / d ) 、x、y都是整数,那么保证原不定整数方程ax+by =
c有解的充要条件就是c / d为整数,即c是gcd(a,b)的倍数。

 

一旦有解,那么令 K = c/d;

 

这就是说,对方程aX+bY =
d;借使有拓展欧几里得求出1组解为(X0,Y0),那么aX0+bY0 =
d;等式两边同时乘以K,即K*( aX0+bY0 ) = d*K =
c;由恒等关系,原方程的解(x0,y0):

 

 X0 = KX0 = c/d * X0,y0 = KY0 = c/d *Y0。

 

不定方程的通解:

       若(x0,y0)是不定整数方程ax+by =
c的1组解,则他的任性整数解都能够表示成(x0+ kb’, y0-ka’),当中a’ =
a/gcd(a,b), b’ = b/gcd(a,b).

 

相关文章