题目描述

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

实现方法如下：

1. 选择两个质数 $p$ 和 $q$，计算 $n=p\times q$。
2. 选择一个质数 $e<\varphi(n)$，计算 $d=e^{-1}\bmod \varphi(n)$。
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)$，分别赋值给 $xn$ 和 $xe$ 这两个变量。

第二个函数是解密函数。

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 与最终评测时有相同的效率和相似的实现，但不要针对评测程序设计攻击代码。最终评测时的程序和下发的程序存在一定差异。

子任务

测试点编号	$n$	$a_i$
$1,2,3$	$\leq 500$	$\leq 10^3$
$4,5,6$	$\leq 8\times 10^3$	$\leq 10^5$
$7,8,9,10$		$\leq 10^{18}$