第七集 突然就什么都不知道了

TimeLimit:1000ms  MemoryLimit:128000KB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description
     “我这是在哪?”小A醒来以后发现自己躺在医院。“还好送来及时,要不然就危险了。”,一位女护士答到。“什么情况,我这是怎么了?”小A疑惑地问。“食物中毒呀,叫你们不要在外面到处乱吃东西,外面都是地沟油、老鼠肉、还有很多不知道的东西,我们一晚上都接收了好几例了,有个女生比你还严重。”女护士叹息道。小A心想难道就是那家九东烤肉,昨晚走在路上肚子一阵剧痛就不省人事了,突然意识到小C肯定也出事了,刚才又听到有个女生更加严重就害怕起来。“女生?是不是一个穿白色裙子长发的女生?”小A激动地问。“对呀!你怎么知道?难道你们一起吃了什么?”护士答到。
    “她现在在哪?我要去看她!”小A激动地想要爬起来,不过全身无力无法起身。护士过来按住他安慰说,“没事了,抢救过来了,只是现在还在昏迷状态。”。小A控制不住流下悔恨的眼泪哭着自言自语,“都是我不好,叫你吃什么九东烤肉!我该死,我该死!!!”。
    第二天,小A恢复比较快,就强忍着虚弱的身体走进小C的病房看她,看她还没醒来就坐在床边的椅子上,握着她的手,看着她苍白的脸不住地怪自己。由于身体虚弱就趴在床边睡着了。过了一会儿小C醒来,看到小A在身边,感觉一阵心酸,因为从来没有人对她真心这么好过。虽然以前很多男生追她,但是都经不起考验,都是假情假意。她突然想起了什么,就赶紧要找她的背包,还好背包也被一起带到了医院放在床边。他赶紧打开包拿出电脑,一连上医院的免费wifi,就有好几个邮件提示弹出来。
    她打开邮件,邮件是一堆乱码,必须拷贝到一个软件输入秘钥解密之后才能看,看了一些之后就突然感觉很不舒服就晕厥过去了。过来好一会儿,小A醒来看见床上多了一台电脑,就觉好奇,拿过来看了下。
    突然看见一个软件上面的图标似曾相识,想起了是小C手臂纹身,便拉开小C袖子,果然一模一样。软件里面写着“女儿,近况如何?你哥过几天会过去给你安排下一个重要任务,务必保管好那两张罗马地图,那可是有关宝藏的机密…”。小A觉得莫名其妙,但是感觉其中有一个重大的阴谋,就看见打开的邮件列表中有一大堆乱码的信。他想一定是靠这个软件来解密,但是这个软件的密码不知道便无法解密,所以他决定破解这个软件。
    他马上破解了这个翻译软件,原来软件中有个字符表从0~31分别是abcdefghijklmnopqrstuvwxyz,.;:!?  (其中符号分别是逗号,点号,分号,冒号,感叹号,问号),翻译邮件的原理是:假设软件的密码是m,将邮件的每个字符所对应字符表的编号和m%32取异或,产生新的编号然后去字符表查找对应的字符。
    但是还是必须知道这个软件的密码,他想密码可能在邮件里面,找了一会儿,他发现有封邮件是有关密码的,上面写着软件密码。他就把密码输入软件,发现不对。这是什么回事,难道改过?那封邮件出现了RSA字眼。“我明白了,这个密码是通过RSA加密后的!”他边想边提取小C电脑中的加密私钥,但是只提取到了公钥,不知道是怎么一回事。但是不管了,能够得到公钥也是可以破解出来私钥的。他想要加快速度,要不然等小C醒来发现不好。
广告时间:“康帅富”教你学算法,各位同学今天科普一下什么是RSA算法,RSA是现今计算机安全的基石,维护了整个互联网世界的和平,现在让我们来认识他。RSA算法会产生公钥和私钥,产生步奏如下:
第一步,随机选择两个不相等的质数p和q。
第二步,计算p和q的乘积n。
第三步,计算n的欧拉函数φ(n)。PS: φ(n)表示小于n且与n互质的数的个数。
第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
第五步,计算e对于φ(n)的模反元素d。
   所谓"模反元素"就是指有一个整数d,可以使得ed被φ(n)除的余数为1。
    ed ≡ 1 (mod φ(n))
第六步,将n和e封装成公钥,n和d封装成私钥。
现在我来教你们如何使用,加密方式:
A 产生公钥和私钥,并将公钥(n,e)告诉B(或者所有人)。
假设B要传递数字m给A,先将m用公钥加密:操作如下c = m^e mod n。
最后后将加密数字c发送给A。
解密方式:
B 将加密的数字c用私钥解密,做如下操作m=c^d mod n得到m。这就是传说中的RSA算法,各位同学看懂了吧?本次学习就到这里,再见!
    他发现公钥里面的数字对(n,e),也知道加密后的密码,他想编个程序输入这些信息和乱码的邮件内容,然后还原出原来的邮件内容。这个程序你会编写吗?
     经过了半个多小时,终于把程序编好,这时候小C突然醒来,看到小A在看着电脑,就不禁紧张地说,“拿我电脑做什么?”
Input
输入包括多组测试数据
每组测试数据有两行
第一行是三个整数n,e,c,其中(n,e)表示小A找到的公钥,c表示加密后的密码。

第二行是被传输的加密文章,文章内只包含字符表内的31个字符。长度不超过100000

 (n=p*q;p和q是2000000以内的质数;1< e < φ(n),且e与φ(n) 互质。0 <= c <= n-1)

Output

 对于每组测试数据,输出翻译后的文章

SampleInput
141 65 46
gfa.kwa,qqq
SampleOutput
iloveyou!!!
Submit
题目统计信息详细
总AC数1
通过人数1
尝试人数3
总提交量8
AC率12.50%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: