Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

アフィン暗号

簡単な暗号法の一つに、アフィン暗号というものがあります。まず、アルファベット a〜z を a = 0, b = 1, c = 2,..., x = 23, y = 24, z = 25 と 0〜25 の数字に置き換えます。そして、以下の式で、原文のアルファベットを置換します。

$F(\gamma) = (\alpha \cdot \gamma + \beta)$ mod $26$

ただし、mod 26 は 26 で割った余りを表します。例えば、$\alpha = 3, \beta = 2$ のとき、アルファベットの 'a' (=0) は、$F(0) = (3 \cdot 0 + 2)$ mod $26 =  2$ で 'c' に、アルファベットの 'n' (=13) は $F(13) = (3 \cdot 13 + 2)$ mod $26 = 15$ で 'p' に置換されます。
このとき、$\gamma$ に対する $F(\gamma)$ が必ず 1 対 1 で対応付けられるように、$\alpha$ と $\beta$ は慎重に選ばれているものとします（$\alpha$ と 26 が互いに素であることが条件）。$\alpha = 4, \beta = 7$ のときのように、$F('a') = 7, F('n') = 7$ と、'a' も 'n' も同じ 'h' に置換されるようなことはありません。また、アルファベット以外の文字は置換されません。

暗号化された文字列を元の文章に復号したものを出力するプログラムを作成してください。元の文章には、キーワードとして

that
this

のいずれかが必ず含まれているものとします。

Input

複数のデータセットが与えられます。１行目にデータセット数 $n$ ($n \leq 30$) が与えられます。続いて $n$ 行のデータが与えられます。各データセットに英小文字と空白からなる 256 文字以内の暗号化された文章が１行に与えられます。

Output

各データセットに対して、復号した元の文章を１行に出力して下さい。

Sample Input

1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw

Output for the Sample Input

i submit that there is another point of view



Sample input:
1
y eazqyp pnop pngtg ye obmpngt xmybp mr lygw


Sample output:
i submit that there is another point of view

Submission status: Accepted

Solution code:
n=int(input())
#最後に97を足せばよい
for i in range(n):
    cty=list(input())
    #αは26と互いに素
    con=[1,3,5,7,9,11,13,15,17,19,21,23,25]
    for alf in con:
        for bet in range(26):
            tmp=0
            voca=[]
            new=[]
            while tmp<len(cty):
                #単語ごとに区切る
                if ord(cty[tmp])<97:
                    new.append(''.join(voca))
                    #print(new)
                    voca=[]
                else:
                    voca.append(chr(((alf*(int(ord(cty[tmp])-97))+bet)%26)+97))
                tmp+=1
            new.append(''.join(voca))
            if 'that'in new or 'this'in new:
                for k in range(len(new)):
                    if k==len(new)-1:
                        print(''.join(new[k]))
                    else:
                        print(''.join(new[k]), end=' ')

Submission status: Accepted

Solution code:
m = [chr(ord('a')+i) for i in range(26)]
t = {}
for i in range(26):
    t[m[i]] = i


def affine(s):
    for a in range(26):
        for b in range(26):
            text = ''.join([m[a * (t[x] - b + 26) % 26]
                            if x != ' ' else ' ' for x in s])
            if 'that' in text or 'this' in text:
                return text


n = int(input())

for i in range(n):
    print(affine(input()))

Submission status: Accepted

Solution code:
n=int(input())
for i in range(n):
    import math
    s=input()
    s_l=list(map(str,s.split()))
    s_ci=[]
    for i in s_l:
        if len(i)==4:
            k_l=[]
            for j in i:
                k=ord(j)-97
                k_l.append(k)
            s_ci.append(k_l)
    a_list=[]
    for i in range(1,1000):
        if math.gcd(i,26)==1:a_list.append(i)
    for a in a_list:
        for b in range(26):
            for k in s_ci:
                word=""
                for l in k:
                    word+=chr(((l*a-b)%26)+97)
                if word=="that" or word=="this":break
            if word=="that" or word=="this":break
        if word=="that" or word=="this":break
    s_l=[]
    for i in s:
        if i==" ":
            s_l.append(-1)
        else:
            k=ord(i)-97
            s_l.append(k)
    ans=""
    for i in s_l:
        if i==-1:ans+=" "
        else:
            ans+=chr(((i*a-b)%26)+97)
    print(ans)

Submission status: Accepted

Solution code:
E = 10**-10
def decy(a):
    return [ord(i)-97 for i in a]
def encr(a):
    return "".join([chr(i+97) for i in a])
def deaffin(j,a,b):
    cont_ = 1
    for i in range(100):
        if cont_ == 0:
            break
        elif ((j-b+26*i)/a)//1 == (j-b+26*i)/a:
            cont_ = 0
            return int((j-b+26*i)/a)%26
n = int(input())
for _ in range(n):
    sen = input()
    words = sen.split()
    wordsl = [len(i) for i in words]
    wordsn = [decy(i) for i in words]
    fourn = []
    for i in range(len(wordsl)):
        if wordsl[i] == 4:
            fourn.append(wordsn[i])
    a_ = 0
    b_ = 0
    cont = 1
    for a in [1,3,5,7,9,11,15,17,19,21,23,25]:
        if cont != 0:
            for b in range(26):
                if cont != 0:
                    for i in fourn:
                        deco = [chr(deaffin(j,a,b)+97) for j in i]
                        if deco == ["t","h","i","s"] or deco == ["t","h","a","t"]:
                            a_ = a
                            b_ = b
                            cont = 0
                            break
    dec_wordsn = [[deaffin(j,a_,b_) for j in i] for i in wordsn]
    dec_words = [encr(i) for i in dec_wordsn]
    print(" ".join(dec_words))

Submission status: Accepted

Solution code:
A_BASE = ord('a')
A = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]

def brute_force(len4s, dwords):
    b = 0
    for a in A:
        while b < 26:
            for word in len4s:
                dec = [(a * r + b) % 26 for r in word]
                if dec in [[19, 7, 8, 18], [19, 7, 0, 19]]:
                    dec_words = [''.join([chr((a*r + b) % 26 + A_BASE) for r in dw]) for dw in dwords]
                    return ' '.join(dec_words)
            b += 1
        b = 0

def solve():
    n = int(input())
    for _ in range(n):
        text = input()
        words = text.split()
        dwords = [[ord(ch) - A_BASE for ch in word] for word in words]
        len4s = [dw for dw in dwords if len(dw) == 4]
        print(brute_force(len4s, dwords))

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
f = sys.stdin


import string

OFFSET = ord('a')

def to_gamma(c):
    return ord(c) - OFFSET

def from_gamma(gamma, alpha, beta):
    return chr((alpha * gamma + beta) % 26 + OFFSET) 

def affine(c, alpha, beta):
    return from_gamma(to_gamma(c), alpha, beta)


# g[0]==g[3]である前提
def search_that(w):
    b = to_gamma(w[2])
    for a in range(26):
        if w[0] == affine('t',a,b) and w[1] == affine('h',a,b):
            return a, b
    return -1, -1

def search_this(g):
    a = (to_gamma(w[0]) - to_gamma(w[3]) + 26) % 26
    for b in range(26):
        if w[0] == affine('t',a,b) and w[1] == affine('h',a,b) and w[2] == affine('i',a,b) and w[3] == affine('s',a,b):
            return a, b
    return -1, -1

def search(w):
    if w[0] == w[3]:
        return search_that(w)
    else:
        return search_this(w)

n = int(f.readline())
for i in range(n):
    line = f.readline().strip()
    words = [word for word in line.split() if len(word) == 4]
    for word in words:
        a, b = search(word)
        if a != -1:
            print(line.translate(str.maketrans(''.join([affine(c, a, b) for c in string.ascii_lowercase]), string.ascii_lowercase)))
            break

Submission status: Runtime Error

Solution code:
def affine_cipher(word,alpha,beta):
    newword = ''
    for c in word:
        newword += w[(alpha*dic[c]+beta)%26]
    return newword

def find_quad_word(sentence):
    r = []
    for word in sentence:
        if len(word)==4:
            r.append(word)
    return r   

def get_alpha_and_beta(quad_word):
    '''return alpha,beta'''
    alpha_list = [i for i in range(26) if  26%i !=0]
    beta_list = [i for i in range(26)]
    for alpha in alpha_list:
        for beta in beta_list:
            tmp = affine_cipher(quad_word,alpha,beta)
            if tmp=='that' or tmp == 'this':
                return alpha,beta
    else:
        pass

def main():
    for i in range(int(raw_input())):
        s = raw_input().split()
        quad_word_list = find_quad_word(s)
        for quad_word in quad_word_list:
            if get_alpha_and_beta(quad_word) is not None:
                alpha,beta = get_alpha_and_beta(quad_word)
                
        new_sentence=[]
        for word in s:
            new_sentence.append(affine_cipher(word,alpha,beta))
        print ' '.join(new_sentence)
        
        
import string
w = string.ascii_lowercase
dic={}
for n,ch in enumerate(w):
     dic[ch]=n

main()

Submission status: Runtime Error

Solution code:
from math import gcd
def unzip(strlist,a,b):
    ret = []
    for word in strlist:
        tmp = ""
        for i in range(len(word)):
            tmp += chr(((ord(word[i])-97)*a+b)%26+97)
        ret.append(tmp)
    return ret

n = int(input())
for _ in range(n):
    instr = input().split()
    for a in range(1,26):
        if gcd(1,26)!=1 : continue
        for b in range(26):
            if "this" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))
            elif "that" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))

Submission status: Runtime Error

Solution code:
list_a = [0,1,3,5,7,9,11,13,15,17,19,21,23]
num_al = {0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i',9:'j',10:'k',11:'l',12:'m',13:'n',14:'o',15:'p',16:'q',17:'r',18:'s',19:'t',20:'u',21:'v',22:'w',23:'x',24:'y',25:'z'}
n = input() + 1
for val in range(1,n):
	num_a = 0
	num_b = 0
	sentence = raw_input()
	words = []
	for val in sentence:
		words.append(val)
	words_num = []
	for val in words:
		if val == 'a':
			words_num.append(0)
		elif val == 'b':
			words_num.append(1)
		elif val == 'c':
			words_num.append(2)
		elif val == 'd':
			words_num.append(3)
		elif val == 'e':
			words_num.append(4)
		elif val == 'f':
			words_num.append(5)
		elif val == 'g':
			words_num.append(6)
		elif val == 'h':
			words_num.append(7)
		elif val == 'i':
			words_num.append(8)
		elif val == 'j':
			words_num.append(9)
		elif val == 'k':
			words_num.append(10)
		elif val == 'l':
			words_num.append(11)
		elif val == 'm':
			words_num.append(12)
		elif val == 'n':
			words_num.append(13)
		elif val == 'o':
			words_num.append(14)
		elif val == 'p':
			words_num.append(15)
		elif val == 'q':
			words_num.append(16)
		elif val == 'r':
			words_num.append(17)
		elif val == 's':
			words_num.append(18)
		elif val == 't':
			words_num.append(19)
		elif val == 'u':
			words_num.append(20)
		elif val == 'v':
			words_num.append(21)
		elif val == 'w':
			words_num.append(22)
		elif val == 'x':
			words_num.append(23)
		elif val == 'y':
			words_num.append(24)
		elif val == 'z':
			words_num.append(25)
		else:
			words_num.append(' ')
	sentence_num = ''
	for val in words_num:
		sentence_num += str(val)
	words_trans = []
	sentence_trans = ''
	while True:
		
		for val in words_num:
			if val == ' ':
				words_trans.append(' ')
			else:
				words_trans.append(num_al[(list_a[num_a] * val + num_b) % 26])
		for val in words_trans:
			sentence_trans += str(val)
		if 'this' in sentence_trans:
			break
		elif 'that' in sentence_trans:
			break
		else:
			words_trans = []
			sentence_trans = ''
			if num_b != 25:
				num_b += 1
			else:
				num_b = 0
				num_a += 1
			continue
	print sentence_trans

Submission status: Runtime Error

Solution code:
list_a = [0,1,3,5,7,9,11,13,15,17,19,21,23]
num_al = {0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i',9:'j',10:'k',11:'l',12:'m',13:'n',14:'o',15:'p',16:'q',17:'r',18:'s',19:'t',20:'u',21:'v',22:'w',23:'x',24:'y',25:'z'}
n = input() + 1
for val in range(1,n):
	num_a = 0
	num_b = 0
	sentence = raw_input()
	words = []
	for val in sentence:
		words.append(val)
	words_num = []
	for val in words:
		if val == 'a':
			words_num.append(0)
		elif val == 'b':
			words_num.append(1)
		elif val == 'c':
			words_num.append(2)
		elif val == 'd':
			words_num.append(3)
		elif val == 'e':
			words_num.append(4)
		elif val == 'f':
			words_num.append(5)
		elif val == 'g':
			words_num.append(6)
		elif val == 'h':
			words_num.append(7)
		elif val == 'i':
			words_num.append(8)
		elif val == 'j':
			words_num.append(9)
		elif val == 'k':
			words_num.append(10)
		elif val == 'l':
			words_num.append(11)
		elif val == 'm':
			words_num.append(12)
		elif val == 'n':
			words_num.append(13)
		elif val == 'o':
			words_num.append(14)
		elif val == 'p':
			words_num.append(15)
		elif val == 'q':
			words_num.append(16)
		elif val == 'r':
			words_num.append(17)
		elif val == 's':
			words_num.append(18)
		elif val == 't':
			words_num.append(19)
		elif val == 'u':
			words_num.append(20)
		elif val == 'v':
			words_num.append(21)
		elif val == 'w':
			words_num.append(22)
		elif val == 'x':
			words_num.append(23)
		elif val == 'y':
			words_num.append(24)
		elif val == 'z':
			words_num.append(25)
		else:
			words_num.append(' ')
	sentence_num = ''
	for val in words_num:
		sentence_num += str(val)
	words_trans = []
	sentence_trans = ''
	while True:
		for val in words_num:
			if val == ' ':
				words_trans.append(' ')
			else:
				words_trans.append(num_al[(list_a[num_a] * val + num_b) % 26])
		for val in words_trans:
			sentence_trans += str(val)
		if 'this' in sentence_trans:
			break
		elif 'that' in sentence_trans:
			break
		else:
			words_trans = []
			sentence_trans = ''
			if num_b != 25:
				num_b += 1
			else:
				num_b = 0
				num_a += 1
			continue
	print sentence_trans

Submission status: Runtime Error

Solution code:
list_a = [0,1,3,5,7,9,11,13,15,17,19,21,23]
num_al = {0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i',9:'j',10:'k',11:'l',12:'m',13:'n',14:'o',15:'p',16:'q',17:'r',18:'s',19:'t',20:'u',21:'v',22:'w',23:'x',24:'y',25:'z'}
n = input() + 1
for val in range(1,n):
	num_a = 0
	num_b = 0
	sentence = raw_input()
	words = []
	for val in sentence:
		words.append(val)
	words_num = []
	for val in words:
		if val == 'a':
			words_num.append(0)
		elif val == 'b':
			words_num.append(1)
		elif val == 'c':
			words_num.append(2)
		elif val == 'd':
			words_num.append(3)
		elif val == 'e':
			words_num.append(4)
		elif val == 'f':
			words_num.append(5)
		elif val == 'g':
			words_num.append(6)
		elif val == 'h':
			words_num.append(7)
		elif val == 'i':
			words_num.append(8)
		elif val == 'j':
			words_num.append(9)
		elif val == 'k':
			words_num.append(10)
		elif val == 'l':
			words_num.append(11)
		elif val == 'm':
			words_num.append(12)
		elif val == 'n':
			words_num.append(13)
		elif val == 'o':
			words_num.append(14)
		elif val == 'p':
			words_num.append(15)
		elif val == 'q':
			words_num.append(16)
		elif val == 'r':
			words_num.append(17)
		elif val == 's':
			words_num.append(18)
		elif val == 't':
			words_num.append(19)
		elif val == 'u':
			words_num.append(20)
		elif val == 'v':
			words_num.append(21)
		elif val == 'w':
			words_num.append(22)
		elif val == 'x':
			words_num.append(23)
		elif val == 'y':
			words_num.append(24)
		elif val == 'z':
			words_num.append(25)
		else:
			words_num.append(' ')
	sentence_num = ''
	for val in words_num:
		sentence_num += str(val)
	words_trans = []
	sentence_trans = ''
	while True:
		for val in words_num:
			if val == ' ':
				words_trans.append(' ')
			else:
				words_trans.append(num_al[(list_a[num_a] * val + num_b) % 26])
		for val in words_trans:
			sentence_trans += str(val)
		if 'this' in sentence_trans:
			break
		elif 'that' in sentence_trans:
			break
		else:
			words_trans = []
			sentence_trans = ''
			if num_b != 26:
				num_b += 1
			else:
				num_b = 0
				num_a += 1
			continue
	print sentence_trans

Submission status: Runtime Error

Solution code:
list_a = [0,1,3,5,7,9,11,13,15,17,19,21,23]
num_al = {0:'a',1:'b',2:'c',3:'d',4:'e',5:'f',6:'g',7:'h',8:'i',9:'j',10:'k',11:'l',12:'m',13:'n',14:'o',15:'p',16:'q',17:'r',18:'s',19:'t',20:'u',21:'v',22:'w',23:'x',24:'y',25:'z'}
n = input() + 1
for val in range(1,n):
	num_a = 0
	num_b = 0
	sentence = raw_input()
	words = []
	for val in sentence:
		words.append(val)
	words_num = []
	for val in words:
		if val == 'a':
			words_num.append(0)
		elif val == 'b':
			words_num.append(1)
		elif val == 'c':
			words_num.append(2)
		elif val == 'd':
			words_num.append(3)
		elif val == 'e':
			words_num.append(4)
		elif val == 'f':
			words_num.append(5)
		elif val == 'g':
			words_num.append(6)
		elif val == 'h':
			words_num.append(7)
		elif val == 'i':
			words_num.append(8)
		elif val == 'j':
			words_num.append(9)
		elif val == 'k':
			words_num.append(10)
		elif val == 'l':
			words_num.append(11)
		elif val == 'm':
			words_num.append(12)
		elif val == 'n':
			words_num.append(13)
		elif val == 'o':
			words_num.append(14)
		elif val == 'p':
			words_num.append(15)
		elif val == 'q':
			words_num.append(16)
		elif val == 'r':
			words_num.append(17)
		elif val == 's':
			words_num.append(18)
		elif val == 't':
			words_num.append(19)
		elif val == 'u':
			words_num.append(20)
		elif val == 'v':
			words_num.append(21)
		elif val == 'w':
			words_num.append(22)
		elif val == 'x':
			words_num.append(23)
		elif val == 'y':
			words_num.append(24)
		elif val == 'z':
			words_num.append(25)
		else:
			words_num.append(' ')
	sentence_num = ''
	for val in words_num:
		sentence_num += str(val)
	words_trans = []
	sentence_trans = ''
	while True:
		for val in words_num:
			if val == ' ':
				words_trans.append(' ')
			else:
				words_trans.append(num_al[(list_a[num_a+1] * val + num_b) % 26])
		for val in words_trans:
			sentence_trans += str(val)
		if 'this' in sentence_trans:
			break
		elif 'that' in sentence_trans:
			break
		else:
			words_trans = []
			sentence_trans = ''
			if num_b != 25:
				num_b += 1
			else:
				num_b = 0
				num_a += 1
			continue
	print sentence_trans

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
from __future__ import (division, absolute_import, print_function,
                        unicode_literals)

from sys import stdin
from string import ascii_lowercase
from itertools import count

def gcd(m, n):
    m, n = sorted([m, n])
    while n:
        m, n = n, m % n
    return m

def encode(char, A, B):
    return chr(((A * (ord(char) - 97) + B) % 26) + 97)

def solve(words):
    for a in (i for i in count(0) if gcd(i, 26) == 1):
        for b in range(26):
            for word in words:
                that = ''.join(encode(c, a, b) for c in 'that')
                if word == that:
                    return (a, b)
                this = ''.join(encode(c, a, b) for c in 'this')
                if word == this:
                    return (a, b)

def main():
    for _ in range(int(stdin.readline())):
        line = stdin.readline()
        a, b = solve([s for s in line.split() if len(s) == 4])
        d = {encode(c, a, b): c for c in ascii_lowercase}
        d[b' '] = b' '
        print(''.join(d[c] for c in line))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
A2Z="abcdefghijklmnopqrstuvwxyz"

def decode(L1,L2,msg):
    x=[]
    for c in msg:
        if 'a'<=c<='z':
            c = L2[L1.index(c)]
        x.append(c)
    return "".join(x)
        
def affine(msg, key):
    a,b = key
    L = [A2Z[(i*a+b)%26] for i in range(26)]
    L = "".join(L)
    return decode(A2Z,L,msg)

def rot(msg, a):
    if a==0: return msg
    a = a % 26
    L = A2Z[a:]+A2Z[:a]
    return decode(A2Z,L,msg)

def find(msg):
    c0=ord('t')
    for i in range(3,26,2):
        x = affine(msg,[i,0])
        a = (c0-ord(x[0]))%26
        x = rot(x,a)
        if x in['this','that']: return [i,a]

n = input()
for i in range(n):
    msg = raw_input()
    for w in msg.split():
        if len(w)==4:
            key = find(w)
            if key!=[]: break
    print affine(msg,key)

Submission status: Runtime Error

Solution code:
A2Z="abcdefghijklmnopqrstuvwxyz"

def decode(L1,L2,msg):
    x=[]
    for c in msg:
        if 'a'<=c<='z':
            c = L2[L1.index(c)]
        x.append(c)
    return "".join(x)
        
def affine(msg, key):
    a,b = key
    L = [A2Z[(i*a+b)%26] for i in range(26)]
    L = "".join(L)
    return decode(A2Z,L,msg)

def rot(msg, a):
    if a==0: return msg
    a = a % 26
    L = A2Z[a:]+A2Z[:a]
    return decode(A2Z,L,msg)

def find(msg):
    c0=ord('t')
    for i in range(3,26,2):
        x = affine(msg,[i,0])
        a = (c0-ord(x[0]))%26
        x = rot(x,a)
        if x in['this','that']: return [i,a]
    return []

n = input()
for i in range(n):
    msg = raw_input()
    for w in msg.split():
        if len(w)==4:
            key = find(w)
            if key!=[]: break
    print affine(msg,key)

Submission status: Runtime Error

Solution code:
dict = ["a","b","c","d","e","f","g","h","i","j","k","l","m",\
        "n","o","p","q","r","s","t","u","v","w","x","y","z"]
lsalpha = [1,3,5,7,9,11,15,17,19,21,23,25]

def deaffine(alpha, beta, code):
    decode = ""
    for chara in code:
        if chara != " ":
            f = dict.index(chara)
            for i in range(26):
                if (alpha*i + beta)%26 == f:
                    dechara = dict[i]
                    break
            decode += dechara
        else:
            decode += " "
    return decode
    
n = int(raw_input())
for roop in range(n):
    code = raw_input()
    for alpha in lsalpha:
        flag = 0
        for beta in range(26):
            deaffine(alpha, beta, code)
            if decode.count("that") > 0 or decode.count("this") > 0:
                flag = 1
                break
        if flag == 1:
            break
    print decode