解：
N= 1889570071
e1 = 1021763679
e2= 519424709
c1= 1244183534 and c2= 732959706
由题意得: c1 = m ^ e1 (mod N), c2 = m ^ e2 (mod N)
由扩展欧几里得算法得: e1·u + e2·v = gcd(e1,e2) = 1
c1^u · c2^v ≡ m^gcd(e1,e2) (mod N)
即是c1^u · c2^v ≡ m (mod N)
其中，c1^u · c2^v (mod N)
= (c1^u mod N · c2^v mod N) mod N
=m mod N
最后解得m
#include<iostream>
using namespace std;
typedef long long L;
L exgcd(L a, L b, L &x, L &y)//ax+by=1返回a,b的gcd，同时求的一组满足题目的最小正整数解
{
L ans, t;
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ans = exgcd(b, a%b, x, y);
t = x;
x = y;
y = t - (a / b)*y;
return ans;
}
L expmod(L a, L b, L n)//快速幂求余算法a^b%n
{
L res = 1;
a %= n;
while (b)
{
if (b & 1)//b是否为奇数
res = (res * a) % n;
a = (a * a) % n;
b /= 2;
}
return res;
}
void main()
{
L n = 1889570071;
L e1 = 1021763679;
L e2 = 519424709;
L c1 = 1244183534;
L c2 = 732959706;
L m, u, v, t, t1, t2, t3;
exgcd(e1, e2, u, v);
cout << u << endl << v << endl;
t1 = expmod(c1, u, n);
t2 = expmod(c2, v, n);
t3 = t1 * t2;
t = expmod(t3, 1, n);
m = t;
cout << m << endl;
}
