UVa 641 Do the Untwist

题目描述密码学涉及秘密通信的方法将明文转换为密文以便只有预期接收者能够解读。本题实现一种称为“扭曲”twisting \texttt{twisting}twisting的简单加密方法。加密时发送方和接收方约定一个正整数密钥k kk。明文和密文是字符数组分别对应整数数组plaincode \texttt{plaincode}plaincode和ciphercode \texttt{ciphercode}ciphercode。数组长度为n nn消息长度下标从0 00开始。字符映射规则为_下划线表示空格对应0 00a到z对应1 11到26 2626.对应27 2727。加密过程如下将明文 plaintext 的每个字符按映射规则转换为整数存入 plaincode。对每个i ii0 ≤ i n 0 \le i n0≤in计算 ciphercode 的第i ii个元素ciphercode [ i ] ( plaincode [ ( k ⋅ i ) m o d n ] − i ) m o d 28 , \textit{ciphercode}[i] (\textit{plaincode}[(k \cdot i) \bmod n] - i) \bmod 28,ciphercode[i](plaincode[(k⋅i)modn]−i)mod28,其中m o d \bmodmod表示非负余数。将ciphercode \texttt{ciphercode}ciphercode中的每个整数再映射回字符得到密文ciphertext \texttt{ciphertext}ciphertext。给定密钥k kk和密文要求还原明文解密。题目保证解唯一且gcd ⁡ ( k , n ) 1 \gcd(k, n) 1gcd(k,n)1。输入格式输入包含一个或多个测试用例每行包含一个整数k kk1 ≤ k ≤ 300 1 \le k \le 3001≤k≤300一个空格然后是一个长度至少为1 11、至多为70 7070的密文字符串。输入以单独一行0结束。输出格式对于每个测试用例输出一行解密后的明文字符串。样例输入5 cs. 101 thqqxw.lui.qswer 3 b_ylxmhzjsys.virpbkr 0输出cat this_is_a_secret beware._dogs_barking题目分析加密的核心是置换与移位。给定密文ciphertext已知每个字符的编码ciphercode[i]以及密钥k kk和长度n nn需要恢复plaincode[j]。由加密公式ciphercode [ i ] ( plaincode [ ( k ⋅ i ) m o d n ] − i ) m o d 28 \textit{ciphercode}[i] (\textit{plaincode}[(k \cdot i) \bmod n] - i) \bmod 28ciphercode[i](plaincode[(k⋅i)modn]−i)mod28设j ( k ⋅ i ) m o d n j (k \cdot i) \bmod nj(k⋅i)modn则上式可改写为plaincode [ j ] ( ciphercode [ i ] i ) m o d 28 \textit{plaincode}[j] (\textit{ciphercode}[i] i) \bmod 28plaincode[j](ciphercode[i]i)mod28因为k kk与n nn互质映射i ↦ ( k ⋅ i ) m o d n i \mapsto (k \cdot i) \bmod ni↦(k⋅i)modn是一个一一对应所以对于每个i ii我们可以得到唯一的j jj并计算出对应的plaincode[j]。最后将plaincode中的整数按字符映射表还原为字符即可得到明文。解题思路建立字符映射表使用数组或map将字符_、a–z、.映射到0 00–27 2727同时建立反向映射表用于将整数还原为字符。对每个测试用例读取密钥k kk和密文字符串令n nn为密文长度。初始化一个长度为n nn的plaintext字符数组。遍历i ii从0 00到n − 1 n-1n−1计算ciphercode[i]即密文第i ii个字符对应的整数。计算j (k * i) % n。计算plaincode[j] (ciphercode[i] i) % 28。将plaincode[j]映射回字符存入plaintext[j]。输出plaintext。由于gcd ⁡ ( k , n ) 1 \gcd(k, n) 1gcd(k,n)1上述赋值不会冲突。复杂度分析每个测试用例处理长度为n nn每次操作O ( 1 ) O(1)O(1)总时间复杂度O ( n ) O(n)O(n)。空间复杂度O ( n ) O(n)O(n)。代码实现// Do the Untwist// UVa ID: 641// Verdict: Accepted// Submission Date: 2016-08-29// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intk;string ciphertext;string letters_abcdefghijklmnopqrstuvwxyz.;mapchar,intcode;for(inti0;iletters.length();i)code[letters[i]]i;while(cink,k){cinciphertext;intnciphertext.length();stringplaintext(n,0);for(inti0;iciphertext.length();i){intmcode[ciphertext[i]];for(intj0;j27;j)if((j-i84)%28m){plaintext[(k*i)%n]letters[j];break;}}coutplaintext\n;}return0;}总结本题通过分析加密公式推导出解密公式利用模运算和映射的置换性质快速还原明文。关键在于理解加密过程的数学本质并注意取模运算的非负性。由于密钥与长度互质保证了每个位置都能唯一确定。该解法简洁高效适用于长度较小的字符串。