拓展欧几里得公式+逆元


题目链接：http://oj.ecustacm.cn/problem.php?id=1456

  1. 对于python选手这题可以直接暴力求解，下面直接上代码 
#from math import *
#n = 1001733993063167141
#k = int(sqrt(n))
#for i in range (2,k):
# if(n%i==0):
# print(i,n//i) 求出p,q的值 运行的时候不要质疑代码 是真的慢
n = 1001733993063167141
d = 212353
p = 891234941
q = 1123984201
tmp=( p - 1)*(q - 1)
print(tmp)
for i in range(2,n+1):
    num = i * tmp + 1
    if(num % d == 0):
        print(num // d)
        break
e=823816093931522017#以上是求e的值
def qpow(a,b,mod):
    ret=1
    while b:
        if(b&1):
            ret = ret * a% mod
        a=a*a%mod
        b>>=1
    return ret
#这是一个快速幂函数
print(qpow(20190324,e,n))

python对大数的处理导致这一题可以说是有手就行，唯一缺点就是求p,q的速度太慢了

  1. 对于c++选手而言这一题却很值得去仔细体会(下面我将会介绍扩展欧几里得算法和逆元，博主也是个萌新，如有错误多多指正)
  • 拓展欧几里得
    扩展欧几里得算法是用来在一直(a,b)是，求解一组(p,q)使得pa+qb=GCD(b,a%b)。
    下面是对该算法的解释和推导(博主字丑勿喷！！！)
//下面就是拓展欧几里得算法
void ex_gcd(ll a,ll b,ll &x,ll &y){
   
    if(!b){
   //当b为0时候特判x=0,y=1
        x=1;
        y=0;
        return ;
    } else {
   
        ex_gcd(b,a%b,x,y);
        int tmp=x;
        x=y;
        y=tmp-(a/b)*y;
    }
}

-逆元
若ax≡1(mod b)，a,b互质，则称x为a的逆元。
根据逆元的定义，可转换为ax+b*y=1,利用拓展欧几里得算法求解。(同时逆元可以用来计算(t / a) mod b时，转换为 t * a的逆元 mod b)。

ll mod_inverse(ll a,ll m){
   
    ll x,y;
    ex_gcd(a,m,x,y);//拓展欧几里得算法，详细可见前文
    return (m+x%m)%m;//为了解决x可能是负值
}

最后，我们将目光拉回到这一题来，有了前文的知识储备那么这个题目就变得简单了，首先利用暴力求出p,q

//p=891234941;
//q=1123984201;
long long int n=1001733993063167141;//c++这块比python快就很离谱了 哈哈哈
for(long long int i=2;i<=sqrt(n);i++){
   
	if(n%i==0){
   
		p=i;
		q=n/i;
		break;
	}
}

由题意可知d*e与(p-1)(q-1)互质，由逆元知识可以知道此时e为d的逆元，那么e的值就很容易求出来了，整个题目的思路就清楚了，下面直接上全部的代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
void ex_gcd(ll a,ll b,ll &x,ll &y){
   //拓展欧几里得
    if(!b){
   
        x=1;
        y=0;
        return ;
    } else {
   
        ex_gcd(b,a%b,x,y);
        int tmp=x;
        x=y;
        y=tmp-(a/b)*y;
    }
}
ll mod_inverse(ll a,ll m){
   //逆元
    ll x,y;
    ex_gcd(a,m,x,y);
    return (m+x%m)%m;
}
//以上两个函数就是为了求逆元的
ll qc(ll a,ll b,ll m){
   
    ll res = 0;
    while(b){
   
        if(b&1) res=(res+a)%m;
        a=(a*2)%m;
        b>>=1;
    }
    return res;
}
ll qm(ll a,ll b,ll m){
   //这里可能有读者很疑惑搞这个快速乘法是为什么 
//博主之前写的时间就没有用快速乘 结果答案溢出了 
//博主认为是n的值太大了(有知道的可以评论区告诉我) 最后加了快速乘法答案才出来了
    ll ans=1;
    a=a%m;
    while(b!=0){
   
        if( b&1 ) ans=qc(ans,a,m)%m;
        a=qc(a,a,m)%m;
        b>>=1;
    }
    return ans;
}
ll n=1001733993063167141;
ll d=212353;
ll c=20190324;
ll p,q;
int main(){
   
    p=891234941;
    q=1123984201;
    ll s=(p-1)*(q-1);
    ll e=mod_inverse(d,s);
    //cout<<e<<endl;//e=823816093931522017
    ll f=qm(c,e,n);
    cout<<f<<endl;//f=579706994112328949
    return 0;
}

希望对读者有所启发，感谢您的支持！！！
没有失望，怎么会有希望呢？