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:
string = 'abcdefghijklmnopqrstuvwxyz'
table = []
for i in string:
    table.append(i)

def encode(string,a,b):
    data = list(string)
    s = []
    flag = 0
    for c in data:
        try:
            i = table.index(c)
            tmp = (a*i+b)%26
            s[-1:] += table[tmp]
        except:
            s.append(' ')
    s = ''.join(s)
    return s

n = int(input())
for x in range(n):
    code = str(input())
    for a in range(26):
        for b in range(26):
            s = encode(code,a,b)
            if 'that' in s:
                print(s)
                break
            elif 'this' in s:
                print(s)
                break

Submission status: Accepted

Solution code:
for _ in range(int(input())):
    s=input()
    for i in range(1,27,2):
        for j in range(27):
            a=[]
            for k in range(len(s)):
                if s[k].islower():a+=chr(((ord(s[k])-97)*i+j)%26+97)
                else:a+=s[k]
            a=''.join(a)
            if 'this' in a or 'that' in a:print(a);break

Submission status: Accepted

Solution code:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    return gcd(b, a%b)

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()
    flag = False
    for a in range(1,26):
        if gcd(1,26)!=1 : continue
        if flag: break
        for b in range(26):
            if "this" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))
                flag = True
                break
            elif "that" in unzip(instr, a, b):
                print(" ".join(unzip(instr, a, b)))
                flag = True
                break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math


N = int(input())
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def encode(s, alpha, beta):
    t = []
    for c in s:
        if c == ' ':
            t.append(c)
        else:
            gamma = ord(c) - 97
            v = (alpha * gamma + beta) % 26
            w = alphabet[v]
            t.append(w)
    return ''.join(t)


for i in range(N):
    s = input().strip()

    for a in range(26):
        for b in range(26):
            encoded = encode(s, a, b)
            if 'that' in encoded or 'this' in encoded:
                print(encoded)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
import os
import math

N = int(input())
alphabet = 'abcdefghijklmnopqrstuvwxyz'

def encode(s, alpha, beta):
    t = []
    for c in s:
        if c == ' ':
            t.append(c)
        else:
            gamma = ord(c) - 97
            v = (alpha * gamma + beta) % 26
            w = alphabet[v]
            t.append(w)
    return ''.join(t)


for i in range(N):
    s = input().strip()
    
    for a in range(0, 26):
        for b in range(0, 26):
            encoded_this = encode('this', a, b)
            encoded_that = encode('that', a, b)
            if encoded_this in s or encoded_that in s:
                encoded_alphabet = encode(alphabet, a, b)
                table = str.maketrans(encoded_alphabet, alphabet)
                dst = s.translate(table)
                print(dst)

Submission status: Accepted

Solution code:
import string

n=int(raw_input())


def decrypt(w,a,b):
    ret=[]
    for i in w:
        ret.append( (i*a+b)%26 )
    return ret
    
for i in range(n):
    inp=[[string.ascii_lowercase.index(c) for c in word] for word in raw_input().split()]
    #that
    that=[string.ascii_lowercase.index(c) for c in 'that']
    #this
    this=[string.ascii_lowercase.index(c) for c in 'this']
    a=0
    b=0
    bkf=0
    for word in inp:
        if len(word)==4:
            for i in range(26):
                for j in range(26):
                    dew=decrypt(word,i,j)
                    if dew==that or dew==this:
                        a=i
                        b=j
                        bkf=1
                        break
                if bkf:
                    break
        if bkf:
            break
    A=[]
    for word in inp:
        dw=decrypt(word,a,b)
        cdw=''.join([string.ascii_lowercase[w] for w in dw])
        A.append(cdw)
    print ' '.join(A)

Submission status: Accepted

Solution code:
# Aizu Problem 0040: Affine Cipher
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")

A_INV = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]

def affine_decode(cipher, a_inv, b):
    message = ""
    for char in cipher:
        if 'a' <= char <= 'z':
            o = ord(char) - 97
            d = (a_inv * o - b) % 26
            message += chr(97 + d)
        else:
            message += char
    return message


N = int(input())
for n in range(N):
    cipher = input().strip()
    for b in range(26):
        for a_inv in A_INV:
            message = affine_decode(cipher, a_inv, b)
            if "this" in message or "that" in message:
                print(message)
                break

Submission status: Accepted

Solution code:
n = int(input())
s = "abcdefghijklmnopqrstuvwxyz"
for i in range(n):
    inp = input()
    for j in range(26):
        for k in range(26):
            out = ""
            for c_inp in inp:
                if c_inp in s:
                    out += s[(s.index(c_inp)*j+k)%26]
                else:
                    out += c_inp
            if ("that" in out) or ("this" in out):
                print(out)

Submission status: Accepted

Solution code:
def F(alpha, beta, c):
    gamma = ord(c) - ord("a")
    return chr((alpha*gamma + beta) % 26 + ord("a"))

alphalist = [1,3,5,7,9,11,15,17,19,21,23,25]
N = int(input())
for lines in range(N):
    S = input()
    words = S.split()
    keyA = -1
    keyB = -1
    for i in range(len(words)):
        if len(words[i]) == 4:
            w = words[i]
            for k in range(len(alphalist)):
                for l in range(26):
                    alpha = alphalist[k]
                    beta = l
                    if F(alpha,beta,w[0]) == "t" and F(alpha,beta,w[1]) == "h":
                        if F(alpha,beta,w[2]) == "a" and F(alpha,beta,w[3]) == "t":
                            keyA = alpha
                            keyB = beta
                        elif F(alpha,beta,w[2]) == "i" and F(alpha,beta,w[3]) == "s":
                            keyA = alpha
                            keyB = beta
                    if keyA > 0:
                        break
                if keyB > 0:
                    break
        if keyA > 0:
            break

    for i in range(len(S)):
        if S[i] == " ":
            print(" ", end="")
        else:
            print(F(keyA,keyB,S[i]), end="")
    print("")

Submission status: Accepted

Solution code:
for _ in[0]*int(input()):
 e=input()
 for i in range(1,26,2):
  for j in range(26):
   a=''.join([c,chr(((ord(c)-97)*i+j)%26+97)][c.islower()]for c in e)
   if'that'in a or'this'in a:print(a);break

Submission status: Accepted

Solution code:
for _ in[0]*int(input()):
 e=input()
 for i in range(26):
  for j in range(26):
   a=''.join([c,chr(((ord(c)-97)*i+j)%26+97)][c.islower()]for c in e)
   if'that'in a or'this'in a:print(a);break

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
for _ in[0]*int(input()):
 e=input()
 for i in range(1,26,2):
  for j in range(26):
   a=''
   for c in e:
    if c in z:a+=z[(z.index(c)*i+j)%26]
    else:a+=c
   if'that'in a or'this'in a:print(a);break

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
for _ in[0]*int(input()):
 e=input()
 for i in range(1,26,2):
  for j in range(26):
   a=''
   for c in e:
    a+=z[(z.index(c)*i+j)%26]if c in z else c
   if'that'in a or'this'in a:print(a);break

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
for _ in[0]*int(input()):
 e=input()
 for i in range(1,26,2):
  for j in range(26):
   a=''.join(z[(z.index(c)*i+j)%26]if c in z else c for c in e)
   if'that'in a or'this'in a:print(a);break

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
def f(x):
 for i in range(1,26,2):
  for j in range(26):
   a=''.join(z[(z.index(c)*i+j)%26]if c in z else c for c in x)
   if'that'in a or'this'in a:return a
for _ in[0]*int(input()):print(f(input()))

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
def g(x,y,s=0,t=1):
 q,r=x//y,x%y
 return g(y,r,t,s-q*t) if r else t
for _ in[0]*int(input()):
 s=input()
 a,b=f()
 h=g(26,a)
 print(''.join(z[h*(z.index(c)-b)%26]if c in z else c for c in s))

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in(1,3,5,7,9,11,15,17,19,21,23,25):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
def g(x,y,s=0,t=1):
 q,r=x//y,x%y
 return g(y,r,t,s-q*t) if r else t
for _ in[0]*int(input()):
 s=input()
 a,b=f()
 h=g(26,a)
 print(''.join(z[h*(z.index(c)-b)%26]if c in z else c for c in s))

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
for _ in[0]*int(input()):
 s=input()
 print(s.translate(str.maketrans(''.join(e(c,*f())for c in z),z)))

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
for _ in[0]*int(input()):
 s=input()
 a=''.join(e(c,*f())for c in z)
 t=str.maketrans(a,z)
 print(s.translate(t))

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
for _ in[0]*int(input()):
 s=input()
 k=f()
 a=''.join(e(c,*k)for c in z)
 t=str.maketrans(a,z)
 print(s.translate(t))

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
for _ in[0]*int(input()):
 s=input()
 k=f()
 print(s.translate(str.maketrans(''.join(e(c,*k)for c in z),z)))

Submission status: Accepted

Solution code:
import sys
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if''.join(e(c,i,j)for c in'that')in s or''.join(e(c,i,j)for c in'this')in s:return(i,j)
input()
for s in sys.stdin:
 s=s.strip()
 k=f()
 print(s.translate(str.maketrans(''.join(e(c,*k)for c in z),z)))

Submission status: Accepted

Solution code:
for n in range(int(input())) :
    s=input()
    for i in range(1,26):
        for j in range(27):
            a=[]
            for k in range(len(s)):
                if s[k].islower():#小文字か判別
                    a+=chr(((ord(s[k])-ord("a"))*i+j)%26+ord("a"))#文字の変換
                else:
                    a+=s[k]
            a="".join(a)
            #print(a)
            if "this" in a or "that" in a:
                print(a)
                break

Submission status: Accepted

Solution code:
z='abcdefghijklmnopqrstuvwxyz'
e=lambda x,i,j:z[(z.index(x)*i+j)%26]
def f():
 for i in range(1,26,2):
  for j in range(26):
   if sum(''.join(e(c,i,j)for c in w)in s for w in['that','this']):return(i,j)
for _ in[0]*int(input()):
 s=input()
 k=f()
 print(s.translate(str.maketrans(''.join(e(c,*k)for c in z),z)))

Submission status: Accepted

Solution code:
base = ord("a")
alst = [i for i in range(3, 26, 2) if i % 13]
def restore(s):
  for a in range(1,26):
    for b in range(26):
      new = "".join([chr((a * (ord(x) - base) + b) % 26 + base) if x != " " else " " for x in s])
      if "that" in new or "this" in new:
        return new

n = int(input())

for _ in range(n):
  print(restore(input()))

Submission status: Accepted

Solution code:
base = ord("a")
alst = [i for i in range(1, 26, 2) if i % 13]
def restore(s):
  for a in alst:
    for b in range(26):
      new = "".join([chr((a * (ord(x) - base) + b) % 26 + base) if x != " " else " " for x in s])
      if "that" in new or "this" in new:
        return new

n = int(input())

for _ in range(n):
  print(restore(input()))

Submission status: Accepted

Solution code:
cv=lambda r,a,b:chr(((ord(r)-97)*a+b)%26+97) if 97<=ord(r)<=122 else r
cv2=lambda x:cv(x,i,j) if 97<=ord(x)<=122 else cv(x.lower(),i,j).upper()

for _ in range(int(input())):
    l=input()
    for i in [1,3,5,7,9,11,15,17,19,21,23,25]:
        for j in range(1,27):
            s="".join(map(cv2,l))
            if "this" in s or "that" in s:
                break
        if "this" in s or "that" in s:
            break
    print(s)

Submission status: Accepted

Solution code:
# AOJ 0040: Affine Cipher
# Python3 2018.6.27 bal4u

M = 26
A = ord('a')

re_prime = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]

def F(ch):
	global a, b
	x = ord(ch)-A
	return chr((a*x + b) % M + A)

dic = {}
for a in re_prime:
	for b in range(M):
		dic[F('t')+F('h')+F('i')+F('s')] = (a, b)
		dic[F('t')+F('h')+F('a')+F('t')] = (a, b)

n = int(input())
for i in range(n):
	s = list(input().split())
	for x in s:
		if len(x) == 4 and x in dic:
			a,b = dic[x]
			break
	tr = {}
	for i in range(M): tr[F(chr(i+A))] = chr(i+A)
	ans = []
	for x in s: ans.append(''.join([tr[c] for c in x]))
	print(*ans)

Submission status: Accepted

Solution code:
from itertools import product

for _ in [0]*int(input()):
    a = [ord(c)-97 for c in input()]

    for p1, p2 in product(range(3, 10000, 2), range(26)):
        text = ""
        for code in a:
            if code == -65:
                text += " "
                continue
            for x in range(26):
                if (p1*x+p2)%26 == code:
                    text += chr(x+97)
                    break

        if "that" in text or "this" in text:
            print(text)
            break

Submission status: Accepted

Solution code:
ALPA = 'abcdefghijklmnopqrstuvwxyz'
sets = dict(zip(list(ALPA), range(26)))
A_LIST = [n for n in range(1, 26) if n%2 != 0 and n%13 != 0]

def encode(word, a, b):
    return [(a*y+b)% 26 for y in [sets[c] for c in list(word)]]

def find(words):
    for a in A_LIST:
        for b in range(26):
            for word in words:
                if word == encode("this", a, b) or word == encode("that", a, b):
                    return (a, b)
                
for i in range(int(raw_input())):
    data = raw_input()
    a, b = find([[sets[c] for c in list(word)] for word in data.split(' ') if len(word) == 4])
    ans = dict(zip(encode(ALPA, a, b), list(ALPA)))
    print ' '.join([''.join([ans[n] for n in [sets[c] for c in list(word)]]) for word in data.split(' ')])

Submission status: Accepted

Solution code:
def affine(s,j,k):
    s1=""
    for c in s:
        if c.isalpha():
            s1+=chr((j*(ord(c)-ord("a"))+k)%26+ord("a"))
        else:
            s1+=c
    return s1

n=input()
for i in range(n):
    s=raw_input()
    this,that="this","that"

    for j in range(26):
        for k in range(26):
            t=affine(s,j,k)
            if (this in t) or (that in t):
                print t
                break

Submission status: Accepted

Solution code:
def decode(s,a,b):
    result=""
    for c in s:
        if c.isalpha():
            result+=chr((a*(ord(c)-ord("a"))+b)%26+ord("a"))
        else:
            result+=c
    return result
for rep in xrange(input()):
    line=raw_input()
    for a in xrange(26):
        for b in xrange(26):
            d=decode(line,a,b)
            if "this" in d or "that" in d:
                print d
                break

Submission status: Accepted

Solution code:

import sys
import re


def lookup(tbl, n):
    for (i,j) in tbl:
        if i == n:
            return j
    else:
        return n

def rlookup(tbl, n):
    for (i,j) in tbl:
        if j == n:
            return i
    else:
        return n


class Affine:
    def __init__(self, a, b):
        tbl = zip(range(27), "abcdefghijklmnopqrstuvwxyz")
        cipher = map(lambda n: lookup(tbl, ((a * n + b) % 26)), range(27))
        self.cipher_table = zip("abcdefghijklmnopqrstuvwxyz", cipher)

    def encrypt(self, str):
        return ''.join(map(lambda c: lookup(self.cipher_table, c), str))

    def decrypt(self, str):
        return ''.join(map(lambda c: rlookup(self.cipher_table, c), str))



r = re.compile("that|this")

sys.stdin.readline()
for line in sys.stdin:
    line = line.rstrip("\r\n")
    for a in [1,3,5,7,9,11,15,17,19,21,23,25]:
        for b in range(26):
            affine = Affine(a, b)
            result = affine.decrypt(line)
            m = r.findall(result)
            if not len(m) == 0:
                 print result

Submission status: Accepted

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' '
        d[b'\n'] = ''
        print(''.join(d[c] for c in line))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(raw_input())
for _ in range(n):
    s = raw_input()
    for a in range(100):
        for b in range(26):
            ss = ''
            for c in s:
                if 'a' <= c <= 'z':
                    ss += chr((a * (ord(c) - 0x61 + b) % 26) + 0x61)
                else:
                    ss += c
            if 'that' in ss or 'this' in ss:
                r = ss
    print r

Submission status: Accepted

Solution code:
n = input()
for i in range(n):
    C = raw_input()
    for A in range(1,26):
        if len([x for x in range(2,26) if 26%x==0 and A%x==0])==0:
            for B in range(26):
                P = ""
                for x in C:
                    if ord("a")<=ord(x)<=ord("z"):
                        P += chr((A*(ord(x)-ord("a"))+B)%26+ord("a"))
                    else:
                        P += x
                if "this" in P or "that" in P:
                    print P

Submission status: Accepted

Solution code:
A2Z="abcdefghijklmnopqrstuvwxyz"

def affine(msg, a, b):
    offset = ord('a')
    x=[]
    for c in msg:
        if 'a'<=c<='z':
            try:
                c = A2Z[(A2Z.index(c)*a+b)%26]
            except:
                print c
        x.append(c)
    return "".join(x)

def rot(msg, a):
    a = a % 26
    L2 = A2Z[a:]+A2Z[:a]
    x = [L2[A2Z.index(c)] for c in msg]
    return "".join(x)

def checkkey(msg):
    c0=('t')
    for i in range(26):#[2,3,5,7,11,13,17,19,23]:
        x = affine(msg,i,0)
        if x[0]!=c0:
            a = (ord(c0)-ord(x[0]))%26
            x = rot(x,a)
        else:
            a = 0
        if x in['this','that']: return i,a
    return -1,-1

n = input()
for i in range(n):
    msg = raw_input()
    for word in msg.split():
        if len(word)==4:
            a,b = checkkey(word)
            if a!=-1: break
    print affine(msg,a,b)

Submission status: Accepted

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(26):
        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: Accepted

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]

n = int(raw_input())
for roop in range(n):
    code = raw_input()
    for alpha in lsalpha:
        flag = 0
        for beta in range(26):
            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 += " "
            if decode.count("that") > 0 or decode.count("this") > 0:
                flag = 1
                break
        if flag == 1:
            break
    print decode

Submission status: Accepted

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 decode(alpha, beta, code):
    msg = ""
    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
            msg += dechara
        else:
            msg += " "
    return msg
    
n = int(raw_input())
for roop in range(n):
    code = raw_input()
    for alpha in lsalpha:
        flag = 0
        for beta in range(26):
            msg = decode(alpha, beta, code)
            if msg.count("that") > 0 or msg.count("this") > 0:
                flag = 1
                break
        if flag == 1:
            break
    print msg

Submission status: Accepted

Solution code:
import string
A2Z="abcdefghijklmnopqrstuvwxyz"

def decode(msg,L):
    t = string.maketrans(A2Z,L)
    s = string.translate(msg,t)
    return s

def affine(msg, a, b):
    L = "".join([A2Z[(i*a+b)%26]for i in range(26)])
    return decode(msg,L)

def rot(msg, a):
    a = a % 26
    L = "".join(A2Z[a:]+A2Z[:a])
    return decode(msg,L)

def checkkey(s):
    c0="t"
    for i in range(26):
        a = 0
        x = affine(s,i,0)
        if x[0]!=c0:
            a = (ord(c0)-ord(x[0]))%26
            x = rot(x,a)
        if x in['this','that']: return i,a
    return -1,-1

n = input()
for i in range(n):
    s = raw_input()
    for w in s.split():
        if len(w)==4:
            a,b = checkkey(w)
            if a!=-1: break
    print affine(s,a,b)

Submission status: Accepted

Solution code:
import string
A2Z="abcdefghijklmnopqrstuvwxyz"
R=range(26)
def decode(msg,L):
    x=""
    for c in msg: x+=(L[A2Z.index(c)] if "a"<=c<="z" else c)
    return x

def affine(msg, a, b):
    L="".join([A2Z[(i*a+b)%26]for i in R])
    s = decode(msg,L)
    return s

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

def checkkey(s):
    c0="t"
    for i in R:
        a = 0
        x = affine(s,i,0)
        c = A2Z.index(x[0])
        if c!=19:
            a = (19-c)%26
            x = rot(x,a)
        if x in['this','that']: return i,a
    return -1,-1

n = input()
while n:
    n-=1
    s = raw_input()
    for w in s.split():
        if len(w)==4:
            a,b = checkkey(w)
            if a!=-1: break
    print affine(s,a,b)

Submission status: Accepted

Solution code:
A2Z="abcdefghijklmnopqrstuvwxyz"

def affine(msg, a, b):
    s=""
    for c in msg: s+=(A2Z[(A2Z.index(c)*a+b)%26] if "a"<=c<="z" else c)
    return s

def rot(msg, a):
    a = a % 26
    L = A2Z[a:]+A2Z[:a]
    s=""
    for c in msg: s+=(L[A2Z.index(c)] if "a"<=c<="z" else c)
    return s

def checkkey(s):
    c0="t"
    for i in range(26):
        a = 0
        x = affine(s,i,0)
        c = A2Z.index(x[0])
        if c!=19:
            a = (19-c)%26
            x = rot(x,a)
        if x in['this','that']: return i,a
    return -1,-1

n = input()
while n:
    n-=1
    s = raw_input()
    for w in s.split():
        if len(w)==4:
            a,b = checkkey(w)
            if a!=-1: break
    print affine(s,a,b)

Submission status: Accepted

Solution code:
A2Z="abcdefghijklmnopqrstuvwxyz"

def affine(msg, a, b):
    s=""
    for c in msg: s+=(A2Z[(A2Z.index(c)*a+b)%26] if "a"<=c<="z" else c)
    return s

def checkkey(s):
    for i in range(26):
        a = 0
        x = affine(s,i,0)
        c = A2Z.index(x[0])
        if c!=19:
            a = (19-c)%26
            x = affine(x,1,a)
        if x in['this','that']: return i,a
    return -1,-1

n = input()
while n:
    n-=1
    s = raw_input()
    for w in s.split():
        if len(w)==4:
            a,b = checkkey(w)
            if a!=-1: break
    print affine(s,a,b)

Submission status: Accepted

Solution code:
for i in range(int(raw_input())):
    s = raw_input()
    for a in range(1, 1000):
        for b in range(26):
            def f(s, a, b):
                return ''.join([chr(((ord(c) - ord('a')) * a + b) % 26 + ord('a')) for c in s])
            if f('that', a, b) in s or f('this', a, b) in s:
                dic = dict([(chr((i * a + b) % 26 + ord('a')), chr(i + ord('a'))) for i in range(26)])
                print ''.join([dic.get(c, c) for c in s])
                break
        else:
            continue
        break

Submission status: Accepted

Solution code:
def encode(string, a, b):
    ret = ''
    for x in string:
        tmp = ord(x) - ord('a')
        if 0 <= tmp <= 26:
            ret += chr((a * tmp + b) % 26 + ord('a'))
        else:
            ret += x
    return ret


n = input()
for t in xrange(n):
    line = raw_input()
    for i in xrange(1, 10000):
        f = False
        if not (26 % i and i % 26):
            continue
        for j in xrange(26):
            txt = encode(line, i, j)
            if 'that' in txt or 'this' in txt:
                print txt
                f = True
                break
        if f:
            break

Submission status: Accepted

Solution code:
from itertools import product

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def decrypt(s):
    for a in range(1, 26, 2):
        if a == 13: continue
        for b in range(26):
            x = ''.join(chr(ord('a') + (a * i + b) % 26) for i in range(26))
            t = s.translate(str.maketrans(x, alphabet))
            if 'this' in t or 'that' in t:
                return t

n = int(input())
for i in range(n):
    s = input()
    print(decrypt(s))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
write = sys.stdout.write
def convert(s, a, b):
    res = []
    ca = ord('a')
    for c in s:
        if c == ' ':
            res.append(" ")
        else:
            res.append(chr((((ord(c) - ca)*a + b) % 26) + ca))
    return "".join(res)

def solve():
    s = readline().strip()
    for a in range(26):
        for b in range(26):
            s1 = convert(s, a, b)
            if "that" in s1 or "this" in s1:
                write(s1)
                write("\n")
T = int(readline())
for i in range(T):
    solve()

Submission status: Accepted

Solution code:
n=int(input())

def GCD(a,b):
    if min(a,b)==0:
        return max(a,b)
    else:
        return GCD(min(a,b),max(a,b)%min(a,b))

def affine(a,b,word):
    retval=""
    for w in word:
        retval+=chr(ord('a')+((ord(w)-ord('a'))*a+b)%26)
    return retval

for i in range(n):
    encrypted=input().split(" ")
    for a in range(1,27):
        for b in range(1,27):
            if GCD(a,26)!=1:
                continue
            plain=[affine(a,b,s) for s in encrypted]
            if ("this" in plain) or ("that" in plain):
                print(" ".join(plain))
                break

Submission status: Accepted

Solution code:
def affine(word, alpha, beta):
    word = list(word)
    for i in range(len(word)):
        ascii = ((ord(word[i]) - ord('a')) * alpha + beta) % 26;
        word[i] = chr(ascii + ord('a'));
    return ''.join(word)
    
alphas = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]

for x in range(int(input())):
    words = input().split(' ')
    for alpha in range(26):
        for beta in range(26):
            string = list(map(lambda x: affine(x, alpha, beta), words))
            if 'that' in string or 'this' in string:
                print(*string)
                break
        else:
            continue
        break