第十届蓝桥杯 RSA解密（C++/ java）

#include <bits/stdc++.h>
using namespace std;
long long n=;
long long d=;
long long c=;
long long p=;
long long q=;
long long e=;
long long phi=(p-)*(q-);
void Ex_gcd(long long a,long long b,long long &x,long long &y)//欧几里得算法求逆元
{
if(b==)
{
x=;
y=;
return ;
}
long long x1,y1;
Ex_gcd(b,a%b,x1,y1);
x=y1;
y=x1-(a/b)*y1;
}
long long quickmul(long long a,long long b)//快速乘求每次的余数
{
long long sum=;
while(b)
{
if(b%==)
sum=(sum+a)%n;
a=(a+a)%n;
b=b/;
}
return sum;
}
long long quickmod(long long a,long long b)//快速幂
{
long long ans=;
while(b)
{
if(b%==)//末位是1；
ans=quickmul(ans,a);//这是直接的回溯法，从最后一位起，如果，如果最后一位是1，则乘a,然后在进行乘以它本身，以为乘1之后一定为偶数，也就是b/2;
a=quickmul(a,a);
b=b/;
}
return ans;
}
int main()
{
long long x,y;
Ex_gcd(d,(q-)*(p-),x,y);
x=(x+phi)%phi;//让x为正
printf("e=%lld\n",x);
printf("ans=%lld\n",quickmod(c,e));
return ;
}

public class Main { // static BigInteger n = new BigInteger("1001733993063167141");
static long n = 1001733993063167141L; //java 大数转为long,记得后面最后面那个是l/L
static long d=212353;
static long c=20190324;
static long p=891234941;
static long q=1123984201;
// static BigInteger e = new BigInteger("823816093931522017");
static long phi=(p-1)*(q-1);
static long e = 1;
static long x1 = 0, y1 = 0;
static long ans = 1; //求解p和q的
// static long p = 2;
// static long q = 0;
// public static void qiue() {
// while(n % p != 0)p++;
// q = n / p;
// } public static long quickmod(long a, long b) { // ---分界线---
long x = 0;
while(b != 0) {
if(b % 2 == 1) {
x = (x + a) % n;
}
a = (a + a) % n;
b /= 2;
}
return x;
}
// 用快速幂求模，每次求模后余数相乘，得到最后的答案
// 每当要用到乘法时，用快速乘，再模，求余数 public static void quickmul(long c, long e) {
while(e != 0) {
if(e % 2 == 1) {
ans = quickmod(ans, c);
}
e /= 2;
c = quickmod(c, c);
}
} // ---分界线--- public static void gcd(long i, long j, long a, long b) { //欧几里得扩展求乘法逆元
if(j == 0) {
x1 = 1;
y1 = 0;
return;
} gcd(j, i % j, x1, y1);
long temp = x1;
x1 = y1;
y1 = temp - i / j * y1;
e = x1;
return ; } public static void main(String[] args){
gcd(d, phi, x1, y1);
e = (e + phi) % phi;
System.out.println(e);
quickmul(c, e);
System.out.print(ans); }
}