题解 P1079 【Vigenère 密码】
顾z
2018-08-25 20:23:43
~~管理员夶 并没有发现这种做法啊!!!~~
### 作者:[@troubler](https://www.luogu.org/space/show?uid=88089)
(原作者亲笔
~~其实是他没实名~~
很容易推出 有明文推出密文的 维哥尼亚密码
即 第 i 行 第 j 列 的秘钥为 r = i + j - 1 ;
所以 给定 j 和 r ，可以得出 i = r - j + 1 ;
所以我用下面的代码打出了一个正表和一个反表
再带入到题意中就可以了
先处理出长度为52的从'a'到'z'的序列：
```cpp
for(int i=1;i<=52;i++)
{
str[i]=char(i%26+96);
cout<<i<<" === ";
cout<<setw(4)<<str[i]<<endl;
}
str[26]='z';str[52]='z';
cout<<endl;
```
再看正表（由明文推密文的密钥）：
```
for(int i=1;i<=26;i++)
{
cout<<"{0,";
for(int j=1;j<=25;j++)
{
a[i][j]=(char)str[i+j-1];
cout<<a[i][j]<<',';
}
a[i][26]=(char)str[i+26-1];
cout<<a[i][26];
cout<<"}"<<endl;
}
cout<<endl;
```
打出来的效果自己可以试试；
（好吧，其实这个没啥用）
然后是反密码表（由密文推明文的密钥）：
```
for(int i=1;i<=26;i++)
{
cout<<"{\"-";
for(int j=1;j<=25;j++)
{
b[i][j]=(char)str[(j-i+1+26)%26];
if(b[i][j]==(char)(0))b[i][j]='z';
cout<<b[i][j];
}
b[i][26]=(char)str[26-i+1];
cout<<b[i][26];
cout<<"\"},"<<endl;
}
```
效果呢
```
{"-abcdefghijklmnopqrstuvwxyz"},
{"-zabcdefghijklmnopqrstuvwxy"},
{"-yzabcdefghijklmnopqrstuvwx"},
{"-xyzabcdefghijklmnopqrstuvw"},
{"-wxyzabcdefghijklmnopqrstuv"},
{"-vwxyzabcdefghijklmnopqrstu"},
{"-uvwxyzabcdefghijklmnopqrst"},
{"-tuvwxyzabcdefghijklmnopqrs"},
{"-stuvwxyzabcdefghijklmnopqr"},
{"-rstuvwxyzabcdefghijklmnopq"},
{"-qrstuvwxyzabcdefghijklmnop"},
{"-pqrstuvwxyzabcdefghijklmno"},
{"-opqrstuvwxyzabcdefghijklmn"},
{"-nopqrstuvwxyzabcdefghijklm"},
{"-mnopqrstuvwxyzabcdefghijkl"},
{"-lmnopqrstuvwxyzabcdefghijk"},
{"-klmnopqrstuvwxyzabcdefghij"},
{"-jklmnopqrstuvwxyzabcdefghi"},
{"-ijklmnopqrstuvwxyzabcdefgh"},
{"-hijklmnopqrstuvwxyzabcdefg"},
{"-ghijklmnopqrstuvwxyzabcdef"},
{"-fghijklmnopqrstuvwxyzabcde"},
{"-efghijklmnopqrstuvwxyzabcd"},
{"-defghijklmnopqrstuvwxyzabc"},
{"-cdefghijklmnopqrstuvwxyzab"},
{"-bcdefghijklmnopqrstuvwxyza"},
```
非常方便的密码反演
这是已经相当于得到了
由密文和密钥推出明文的公式（规则），
将表赋入 r 数组用 r 转化一下就OK了
最后的简单代码（注意 a串 和 b串 顺序和取模就好了 ）：
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#define ll long long
#define E 1007
using namespace std;
char r[E][E]={
{""},
{"-abcdefghijklmnopqrstuvwxyz"},
{"-zabcdefghijklmnopqrstuvwxy"},
{"-yzabcdefghijklmnopqrstuvwx"},
{"-xyzabcdefghijklmnopqrstuvw"},
{"-wxyzabcdefghijklmnopqrstuv"},
{"-vwxyzabcdefghijklmnopqrstu"},
{"-uvwxyzabcdefghijklmnopqrst"},
{"-tuvwxyzabcdefghijklmnopqrs"},
{"-stuvwxyzabcdefghijklmnopqr"},
{"-rstuvwxyzabcdefghijklmnopq"},
{"-qrstuvwxyzabcdefghijklmnop"},
{"-pqrstuvwxyzabcdefghijklmno"},
{"-opqrstuvwxyzabcdefghijklmn"},
{"-nopqrstuvwxyzabcdefghijklm"},
{"-mnopqrstuvwxyzabcdefghijkl"},
{"-lmnopqrstuvwxyzabcdefghijk"},
{"-klmnopqrstuvwxyzabcdefghij"},
{"-jklmnopqrstuvwxyzabcdefghi"},
{"-ijklmnopqrstuvwxyzabcdefgh"},
{"-hijklmnopqrstuvwxyzabcdefg"},
{"-ghijklmnopqrstuvwxyzabcdef"},
{"-fghijklmnopqrstuvwxyzabcde"},
{"-efghijklmnopqrstuvwxyzabcd"},
{"-defghijklmnopqrstuvwxyzabc"},
{"-cdefghijklmnopqrstuvwxyzab"},
{"-bcdefghijklmnopqrstuvwxyza"},
};
char a[E],b[E];
bool upb[E];
int main()
{
cin>>a>>b;
ll lena=strlen(a);
ll lenb=strlen(b);
for(int i=0;i<lena;i++)
{
if((ll)a[i] < 96) a[i]=(char)((ll)a[i]+32);
}
for(int i=0;i<lenb;i++)
{
if((ll)b[i] < 96) b[i]=(char)((ll)b[i]+32),upb[i]=1;
}
for(int i=0;i<lenb;i++){
char u=b[i];
char v=a[(i)%lena];
if(i%lenb==0)v=a[lenb];
if(i==0)v=a[0];
if(upb[i]==0)
cout<<r[(ll)v-96][(ll)u-96];
else
cout<<(char)((ll)r[(ll)v-96][(ll)u-96]-32);
}
return 0;
}
```
（感谢打赏！）