[NOIP2012-提高] Vigenère 密码

题目描述

给定密钥串 $k$ 和密文串 $C$ （都只含大小写字母），Vigenère 加密是逐位模 26 加法 $c_i \equiv m_i + k_{i \bmod n} \pmod{26}$ ，运算忽略大小写，密钥不足时循环复用；求明文 $M$ 。输入两行：第一行密钥（长度不超过 100），第二行密文（长度不超过 1000）；输出一行明文。样例输入 CompleteVictory / Yvqgpxaimmklongnzfwpvxmniytm，样例输出 Wherethereisawillthereisaway。

思路

加密是逐位模 26 加法，解密就是逐位模 26 减法 $m_i = (c_i - k_{i \bmod n}) \bmod 26$ 。把 $c_i$ 、 $k_i$ 都转小写做数值运算，负数加 26 归正，最后按密文自身的大小写还原。密钥下标用 $i \bmod n$ 取即可循环复用，整体 $O(m)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 09:53
# update_at: 2026-10-02 09:53

import sys


def undo(ch: str, kch: str) -> str:
    """® 运算的逆：明文字母 = 密文字母 − 密钥字母（mod 26），忽略大小写、大小写取自密文。"""
    plain = (ord(ch.lower()) - ord(kch.lower())) % 26  # 明文在字母表中的序号 A=0
    return chr(plain + ord('A' if ch.isupper() else 'a'))


def solve() -> None:
    lines = [ln.strip() for ln in sys.stdin.read().splitlines() if ln.strip()]
    key = lines[0]    # 密钥，长度 ≤ 100，只有字母
    cipher = lines[1]  # 密文，长度 ≤ 1000；密钥不足时循环重复使用
    # 逐位用密钥对应字母解密一个字母，密钥下标 i % len(key) 即"重复使用"的落点
    print(''.join(undo(ch, key[i % len(key)]) for i, ch in enumerate(cipher)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 14:55
 * update_at: 2026-10-06 14:55
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

string key;    // 密钥串，长度不超过 100，仅含字母
string cipher; // 密文串，长度不超过 1000，仅含字母，密钥不足时循环使用

// 求单个密文字母的明文：按密文自身大小写解码，'A'/'a' 为 0
char decode_char(char c, char k) {
    int cv = tolower(c) - 'a';          // 密文数值
    int kv = tolower(k) - 'a';          // 密钥数值
    int mv = (cv - kv + 26) % 26;       // 模 26 减法，负数加 26 回到 [0,26)
    char base = isupper(c) ? 'A' : 'a'; // 大小写沿用密文
    char plain_char = base + mv;
    return plain_char;
}

int main() {
    cin >> key >> cipher;

    ll n = key.size();
    ll m = cipher.size();
    string plain;
    // 逐位解密，密钥下标 i % n 实现密钥循环重复使用
    for (ll i = 0; i < m; i++) {
        plain += decode_char(cipher[i], key[i % n]);
    }

    cout << plain << endl;
    return 0;
}

[NOIP2012-提高] Vigenère 密码

目录

题目描述

思路

参考代码