UVa 641 Do the Untwist

题目描述

密码学涉及秘密通信的方法，将明文转换为密文以便只有预期接收者能够解读。本题实现一种称为“扭曲”（twisting \texttt{twisting}twisting）的简单加密方法。加密时，发送方和接收方约定一个正整数密钥k kk。明文和密文是字符数组，分别对应整数数组plaincode \texttt{plaincode}plaincode和ciphercode \texttt{ciphercode}ciphercode。数组长度为n nn（消息长度），下标从0 00开始。

字符映射规则为：'_'（下划线，表示空格）对应0 00，'a'到'z'对应1 11到26 2626，'.'对应27 2727。加密过程如下：

1. 将明文 plaintext 的每个字符按映射规则转换为整数，存入 plaincode。
2. 对每个i ii（0 ≤ i < n 0 \le i < n0≤i<n），计算 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表示非负余数。
3. 将ciphercode \texttt{ciphercode}ciphercode中的每个整数再映射回字符，得到密文ciphertext \texttt{ciphertext}ciphertext。

给定密钥k kk和密文，要求还原明文（解密）。题目保证解唯一，且gcd ⁡ ( k , n ) = 1 \gcd(k, n) = 1gcd(k,n)=1。

输入格式

输入包含一个或多个测试用例，每行包含一个整数k kk（1 ≤ 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中的整数按字符映射表还原为字符，即可得到明文。

解题思路

1. 建立字符映射表：使用数组或map将字符'_'、'a'–'z'、'.'映射到0 00–27 2727，同时建立反向映射表用于将整数还原为字符。
2. 对每个测试用例：
   • 读取密钥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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intk;string ciphertext;string letters="_abcdefghijklmnopqrstuvwxyz.";map<char,int>code;for(inti=0;i<letters.length();i++)code[letters[i]]=i;while(cin>>k,k){cin>>ciphertext;intn=ciphertext.length();stringplaintext(n,'0');for(inti=0;i<ciphertext.length();i++){intm=code[ciphertext[i]];for(intj=0;j<=27;j++)if((j-i+84)%28==m){plaintext[(k*i)%n]=letters[j];break;}}cout<<plaintext<<'\n';}return0;}

总结

本题通过分析加密公式，推导出解密公式，利用模运算和映射的置换性质快速还原明文。关键在于理解加密过程的数学本质，并注意取模运算的非负性。由于密钥与长度互质，保证了每个位置都能唯一确定。该解法简洁高效，适用于长度较小的字符串。