【LibreOJ】#6392. 「THUPC2018」密码学第三次小作业 / Rsa 扩展欧几里得算法

【题目】#6392. 「THUPC2018」密码学第三次小作业 / Rsa
【题意】T次询问，给定正整数c1,c2,e1,e2,N，求正整数m满足：
(c_1=m^{e_1} mod N)
(c_2=m^{e_2} mod N)
保证(c_1,c_2,e_1,e_2 leq N,2^8 < N < 2^{63},T leq 10^4,(e_1,e_2)=1,(m,N)=1)。
【算法】扩展欧几里得算法
我们最终要求(m)，而已知(m^{e_1})和(m^{e_2})，容易考虑辗转相除法。每次将((e_1,e_2))更新为((e_2,e_1 \% e_2))，那么值的变化就是从((c_1,c_2))更新为((c_2,frac{c_1}{c_2^{e_1/ e_2}}))。这样辗转相除到(e_2=0)为止，此时(c_1)就是答案。
过程中要注意：long long范围内的乘法要用快速乘（包括快速幂）。由于不保证N是素数所以不能用费马小定理，必须用扩欧求解逆元。
复杂度(O(T log^3n))。

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,e1,e2,c1,c2;
ll M(ll x){return x>=n?x-n:x;}
ll pows(ll x,ll k){ll ans=0;while(k){if(k&1)ans=M(ans+x);x=M(x+x);k>>=1;}return ans;}
ll power(ll x,ll k){ll ans=1;while(k){if(k&1)ans=pows(ans,x);x=pows(x,x);k>>=1;}return ans;}
void exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;}else{exgcd(b,a%b,y,x);y-=x*(a/b);}}
ll inv(ll a){ll x,y;exgcd(a,n,x,y);return (x%n+n)%n;}
void gcd(ll a,ll b){
	if(!b)return;else{swap(c1,c2);c2=pows(c2,inv(power(c1,a/b)));gcd(b,a%b);}
}
int main(){
	int T;scanf("%d",&T);
	while(T--){
		scanf("%lld%lld%lld%lld%lld",&c1,&c2,&e1,&e2,&n);
		gcd(e1,e2);
		printf("%lld
",c1);
	}
	return 0;
}

然后看了官方正解后发现，这种做法的本质就是扩展欧几里得算法。由于：

$$m^1=m^{e_1s+e_2t}=(m^{e_1})^s(m^{e_2})^t=(c_1)^s(c_2)^t$$

于是用扩展欧几里得算法解出s和t，然后快速幂计算即可（负数先算逆元再快速幂）。