[CQOI2016] 密钥破解

一种非对称加密算法的密钥生成过程如下： 1.任选两个不同的质数$p,q$ 2.计算$N=p \times q$，$r=(p-1)(q-1)$ 3.选取小于$r$，且与$r$互质的整数$e$ 4.计算整数$d$，使得$ed≡1(mod r)$ 5.二元组$(N,e)$称为公钥，二元组$(N,d)$称为私钥。 当需要加密消息$n$时，（假设$n$是一个小于$N$的整数，因为任何格式的消息都可转为整数表示），使用公钥$(N,e)$，按照 $$n^e≡c(mod N)$$ 运算，可得到密文$c$ 对密文$c$解密时，用私钥$(N,d)$，按照 $$c^d≡n(mod N)$$ 运算，可得到原文 $n$。算法正确性证明省略。 由于用公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥由消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。 现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破解出私钥，并据此解密密文。

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

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

3 187 45

107 12

对于$30\%$的数据，$e,N,c \le 2^{20}$； 对于$100\%$的数据，$e,N,c \le 2^{62},c<N$