10434: #2045. 「CQOI2016」密钥破解

内存限制：256 MB 时间限制：1.000 S 提交：0 解决：0
评测方式：文本比较 命题人：

题目描述

一种非对称加密算法的密钥生成过程如下：

  1. 任选两个不同的质数 p,qp, qp,q；
  2. 计算 N=pq,r=(p−1)(q−1)N = pq, r=(p-1)(q-1)N=pq,r=(p−1)(q−1)；
  3. 选取小于 rrr，且与 rrr 互质的整数 eee；
  4. 计算整数 ddd，使得 ed≡1(modr)；
  5. 二元组 (N,e)(N, e)(N,e) 称为公钥，二元组 (N,d)(N, d)(N,d) 称为私钥。

当需要加密消息 nnn 时（假设 nnn 是一个小于 NNN 的整数，因为任何格式的消息都可转为整数表示），使用公钥 (N,e)(N, e)(N,e)，按照

ne≡c(modN)

运算，可得到密文 ccc。

对密文 ccc 解密时，用私钥 (N,d)(N, d)(N,d)，按照

cd≡n(modN)

运算，可得到原文 nnn。算法正确性证明省略。

由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。

现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。

输入格式

输入文件内容只有一行，为空格分隔的三个正整数 e,N,ce, N, ce,N,c。

输出格式

输出文件内容只有一行，为空格分隔的两个整数 d,nd, nd,n。

样例

样例输入

3 187 45

样例输出

107 12

样例解释

样例中 p=11,q=17p = 11, q = 17p=11,q=17。

数据范围与提示

对于 30%30\%30% 的数据，e,N,c≤220e, N, c \leq 2^{20}e,N,c≤2​20​​；
对于 100%100\%100% 的数据，1≤e,N,c≤262,c<N1 \leq e, N, c \leq 2^{62}, c < N1≤e,N,c≤2​62​​,c<N。