该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

传信

2s|512Mb

有两个oier上课传纸条，他们不想被其他同学知道他们纸条的内容。于是他们决定进行RSA加密。

实现方法如下：

1. 选择两个质数 $p$ 和 $q$, 计算 $n=p \cdot q$ 。

2. 选择一个质数 $e<\varphi(n)$, 计算 $d=e^{-1} \bmod \varphi(n)$ 。

$\varphi(n)$是欧拉函数，$\varphi(n)$表示$1-n$中有多少数与$n$互质。特别的$\varphi(1)=1$

3. 如果加密的信息为 $m$, 那么加密后的 $c=m^{e} \bmod n$, 这里的 $e$ 和 $n$ 称为 公钥 。

4. 如果加密后的信息为 $c$, 那么原信息 $m=c^{d} \bmod n$ 。

实现

本题是一道非传统题，你需要实现一个支持加密方式生成和解密的程序 message.cpp 。

这个程序需要包含以下两个函数：

第一个函数是初始化函数。

void init (long long &xn, long long &xe);

请任意生成一组公钥 $(n, e)$, 分别赋值给 $x n$ 和 $x e$ 这两个变量。 第二个函数是解密函数。

long long decrypt (long long c );

$传入的参数$$c$ 是加密后的信息，返回值是原信息 $m$ 。

样例交互库

样例交互库 grader.cpp 模拟了最终评测时的交互方式。

它从 message.in 中读入数据，并将结果输出到 message.out 中。

样例交互库的输入格式

第一行一个正整数 $n$, 表示共有 $n$ 个数需要由样例交互库加密后提供给你的程序解密。

接下来每 $n$ 行，每行一个正整数 $a_{i}$, 表示加密的数为 $a_{i}$ 。

样例交互库的样例输入

5

6554759 

76564657 

8121 

30525 

2777735

交互库的使用

在本地测试时，请把提供的 grader.cpp 放在和 message.cpp 同一目录 下，并在 message.cpp 的 第 一行 写上对交互库的引用：

#include "grader.cpp"

在选手工作目录的 sample/message 下给出了一些参考文件。

其中， message.cpp 是一份代码模板，你可以对其进行修改，实现自己的算法逻辑。 grader.cpp 是样例交库， message - sample.in 是样例交互库的样例输入文件。 message.h 是相关头文件，请始终将其放置在互交互库所在目录中。

题目要求实现两个函数并不意味着你的 message.cpp 中只能包含两个函数。你可以定义其他函数以辅助程序设计。

你的程序不得进行任何文件读写操作，否则将计为$0$分。

你可以认为下发的 grader.cpp 与最终评测时有相同的效率和相似的实现，但不要针对评测程序设计攻击代码。最终评测时的程序和下发的程序存在一定差异。

http://bzoj.org/file/2/message.zip --下发文件 http://bzoj.org/d/dxlc2021/file/2/grader.cpp --更新一个正常的grader.cpp

子任务