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: Wrong Answer

Solution code:
from itertools import product
n = int(input())
for _ in range(n):
    s = input()
    for alpha,beta in product([3,5,7,9,11,15,17,19,21,23,25],range(26)):
        g = "".join(chr((alpha*(ord(e)-ord("a"))+beta)%26+ord("a")) if not e == " " else " "  for e in s)
        if "that" in g or "this" in g: print(g); break

Submission status: Wrong Answer

Solution code:
# Edit : 2014/11/16
# Lang : Python3
# Time : 00.  s
# judge: not Accepted

# File: pc0021.py

from itertools import product


if __name__ == "__main__":

    mycode0 = "abcdefghijklmnopqrstuvwxyz"
    mycode1 = {
        "a": 0,
        "b": 1,
        "c": 2,
        "d": 3,
        "e": 4,
        "f": 5,
        "g": 6,
        "h": 7,
        "i": 8,
        "j": 9,
        "k": 10,
        "l": 11,
        "m": 12,
        "n": 13,
        "o": 14,
        "p": 15,
        "q": 16,
        "r": 17,
        "s": 18,
        "t": 19,
        "u": 20,
        "v": 21,
        "w": 22,
        "x": 23,
        "y": 24,
        "z": 25,
    }

    nset = int(input())
    # nset = 1



    for i in range(0, nset):

        inl = ""
        outl = ""

        inl = input()

        for a, b in product(range(1, 26, 2), range(1, 26)):
            outl = ""
            if a == 13:
                continue
            #print(a, b)

            for i in range(0, len(inl)):
                if inl[i] == " ":
                    #print(" ")
                    outl += " "
                else:
                    #print(inl[i], mycode1[inl[i]], mycode0[mycode1[inl[i]]])
                    decode = (a * mycode1[inl[i]] + b) % 26
                    #print(mycode0[decode])
                    #outl[i] = mycode0[decode]
                    outl += mycode0[decode]
            if "this" in outl or "that" in outl :
                    print(outl)

                    #

Submission status: Wrong Answer

Solution code:
# Edit : 2014/11/16
# Lang : Python3
# Time : 00.  s
# judge: not Accepted

# File: pc0021.py

from itertools import product


if __name__ == "__main__":

    mycode0 = "abcdefghijklmnopqrstuvwxyz"
    mycode1 = {
        "a": 0,
        "b": 1,
        "c": 2,
        "d": 3,
        "e": 4,
        "f": 5,
        "g": 6,
        "h": 7,
        "i": 8,
        "j": 9,
        "k": 10,
        "l": 11,
        "m": 12,
        "n": 13,
        "o": 14,
        "p": 15,
        "q": 16,
        "r": 17,
        "s": 18,
        "t": 19,
        "u": 20,
        "v": 21,
        "w": 22,
        "x": 23,
        "y": 24,
        "z": 25,
    }

    nset = int(input())
    for i in range(0, nset):

        inl = input()

        for a, b in product(range(1, 26, 2), range(1, 26)):
            outl = ""
            if a == 13:
                continue
            # print(a, b)

            for i in range(0, len(inl)):
                if inl[i] == " ":
                    # print(" ")
                    outl += " "
                else:
                    # print(inl[i], mycode1[inl[i]], mycode0[mycode1[inl[i]]])
                    decode = (a * mycode1[inl[i]] + b) % 26
                    #print(mycode0[decode])
                    #outl[i] = mycode0[decode]
                    outl += mycode0[decode]
            if "this" in outl or "that" in outl:
                print(outl)
                continue

                #

Submission status: Wrong Answer

Solution code:
# Edit : 2014/11/16
# Lang : Python3
# Time : 00.  s
# judge: not Accepted

# File: pc0021.py

from itertools import product


if __name__ == "__main__":

    mycode0 = "abcdefghijklmnopqrstuvwxyz"
    mycode1 = {
        "a": 0,
        "b": 1,
        "c": 2,
        "d": 3,
        "e": 4,
        "f": 5,
        "g": 6,
        "h": 7,
        "i": 8,
        "j": 9,
        "k": 10,
        "l": 11,
        "m": 12,
        "n": 13,
        "o": 14,
        "p": 15,
        "q": 16,
        "r": 17,
        "s": 18,
        "t": 19,
        "u": 20,
        "v": 21,
        "w": 22,
        "x": 23,
        "y": 24,
        "z": 25,
    }

    nset = int(input())
    for i in range(0, nset):

        inl = input()
        for a, b in product(range(1, 26, 2), range(1, 26)):
            outl = ""
            if a == 13:
                continue
            # print(a, b)

            for i in range(0, len(inl)):
                #if inl[i] == " ":
                #    outl += " "
                if inl[i] not in mycode1:
                    outl += inl[i]
                else:
                    decode = (a * mycode1[inl[i]] + b) % 26
                    outl += mycode0[decode]
            if "this" in outl or "that" in outl:
                print(outl)
                continue

                # i submit that there is another point of view
                # i submit that there is another point of view

Submission status: Wrong Answer

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 i>2 and 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: Wrong Answer

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 i>1 and 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: Wrong Answer

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 i>1 and 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
       
import string
w = string.ascii_lowercase
dic={}
for n,ch in enumerate(w):
     dic[ch]=n

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)

Submission status: Wrong Answer

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
#start = time.clock()

def op(a,b):
    for i in tmp:
        for j in i:
            x=''
            for k in j:
                x+=chr((((ord(k)-97)*a+b)%26)+97)
            print x,
        print
    exit()

n=int(raw_input())
ans=[0]*3
#n,k=map(int,raw_input().split())
tmp=[]
for i in range(n):
    tmp.append(raw_input().split())

for i in tmp:
    for j in i:
        if len(j)==4:
            for a in range(1,101):
                if gcd(a,26)!=1:
                    continue
                for b in range(26):
                    s=''
                    for q in j:
                        s+=chr((((ord(q)-97)*a+b)%26)+97)
                    if s=='that' or s=='this':
                        op(a,b)

Submission status: Wrong Answer

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
#start = time.clock()

def op(a,b):
    for i in tmp:
        for j in i:
            x=''
            for k in j:
                x+=chr((((ord(k)-97)*a+b)%26)+97)
            print x,
        print
    exit()

n=int(raw_input())
ans=[0]*3
#n,k=map(int,raw_input().split())
tmp=[]
for i in range(n):
    tmp.append(raw_input().split())

for i in tmp:
    for j in i:
        if len(j)==4:
            for a in range(1,10001):
                if gcd(a,26)!=1:
                    continue
                for b in range(26):
                    s=''
                    for q in j:
                        s+=chr((((ord(q)-97)*a+b)%26)+97)
                    if s=='that' or s=='this':
                        op(a,b)

Submission status: Wrong Answer

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
#start = time.clock()

def op(a,b):
    for i in tmp:
        x=''
        for k in i:
            x+=chr((((ord(k)-97)*a+b)%26)+97)
        print x,
    print
    return

n=int(raw_input())
ans=[0]*3
#n,k=map(int,raw_input().split())
tmp=[]
for h in range(n):
    tmp=raw_input().split()
    for i in tmp:
        if len(i)==4:
            for a in range(26):
                if gcd(a,26)!=1:
                    continue
                for b in range(26):
                    s=''
                    for q in i:
                        s+=chr((((ord(q)-97)*a+b)%26)+97)
                    if s=='that' or s=='this':
                        op(a,b)

Submission status: Wrong Answer

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
#start = time.clock()

def op(a,b):
    ans=[]
    for i in tmp:
        x=''
        for k in i:
            x+=chr((((ord(k)-97)*a+b)%26)+97)
        ans.append(x)
    print ' '.join(ans)
    return

n=int(raw_input())
#n,k=map(int,raw_input().split())
tmp=[]
for h in range(n):
    tmp=raw_input().split()
    for i in tmp:
        if len(i)==4:
            for a in range(26):
                if gcd(a,26)!=1:
                    continue
                for b in range(26):
                    s=''
                    for q in i:
                        s+=chr((((ord(q)-97)*a+b)%26)+97)
                    if s=='that' or s=='this':
                        op(a,b)

Submission status: Wrong Answer

Solution code:
#encoding=utf-8

import sys
printf = sys.stdout.write

def inp():
    word = []
    x = input()
    for i in xrange(x):
    	w = raw_input().split()
        for j in xrange(len(w)):
            if len(w[j]) == 4:
                word.append(w[j])
        A, B = syori(word)

    for i in xrange(len(w)):
        for j in xrange(len(w[i])):
            printf(chr(((A*(ord(w[i][j]) - 97) - B) % 26) + 97))
        printf(" ")

        
       

def syori(w):
    tako, ans = [], []
    for A in xrange(1,26,2):
        for B in xrange(26):
            for i in xrange(len(w)):
                for j in xrange(len(w[i])):
                    tako.append(chr(((A*(ord(w[i][j]) - 97) - B) % 26) + 97))
            for j in xrange(len(w)):
                ans.append("".join(tako[0+4*j:(j+1)*4]))
            for k in xrange(len(ans)):
                if ans[k] == "this" or ans[k] == "this":
                    return A,B
                elif ans[k] == "that" or ans[k] == "that":
                    return A,B

            tako, ans = [], []
				
if __name__ == "__main__":
    inp()

Submission status: Wrong Answer

Solution code:
#encoding=utf-8

import sys
printf = sys.stdout.write

def inp():
    word = []
    x = input()
    for i in xrange(x):
    	w = raw_input().split()
        for j in xrange(len(w)):
            if len(w[j]) == 4:
                word.append(w[j])
        A, B = syori(word)

    for i in xrange(len(w)):
        for j in xrange(len(w[i])):
            printf(chr(((A*(ord(w[i][j]) - 97) - B) % 26) + 97))
        print " ",
       

def syori(w):
    tako, ans = [], []
    for A in xrange(1,26,2):
        for B in xrange(26):
            for i in xrange(len(w)):
                for j in xrange(len(w[i])):
                    tako.append(chr(((A*(ord(w[i][j]) - 97) - B) % 26) + 97))
            for j in xrange(len(w)):
                ans.append("".join(tako[0+4*j:(j+1)*4]))
            for k in xrange(len(ans)):
                if ans[k] == "this" or ans[k] == "this":
                    return A,B
                elif ans[k] == "that" or ans[k] == "that":
                    return A,B

            tako, ans = [], []
				
if __name__ == "__main__":
    inp()

Submission status: Wrong Answer

Solution code:
def affine(word, alpha, beta):
    word = list(word)
    for i in range(len(word)):
        word[i] = albs[(albs.index(word[i]) * alpha + beta) % 26]
    return ''.join(word)
albs = 'abcdefghijklmnopqrstuvwxyz'
alphas = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
betas = list(range(26))
for _ in range(int(input())):
    words = input().split(' ')
    for alpha in alphas:
        for beta in betas:
            words = list(map(lambda x: affine(x, alpha, beta), words))
            if 'that' in words or 'this' in words:
                print(*words)
                break
        else:
            continue
        break

Submission status: Wrong Answer

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 i in range(n):
    code = str(input())
    for a in range(1,26):
        for b in range(1,26):
            s = encode(code,a,b)
            if 'that' in s or 'this' in s:
                print(s)

Submission status: Wrong Answer

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 i in range(n):
    code = str(input())
    for a in range(1,26):
        for b in range(1,26):
            s = encode(code,a,b)
            if 'that' in s:
                print(s)
            elif 'this' in s:
                print(s)

Submission status: Wrong Answer

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 i in range(n):
    code = str(input())
    for a in range(1,26):
        for b in range(1,26):
            s = encode(code,a,b)
            if 'that' in s:
                print(s)
                break
            elif 'this' in s:
                print(s)
                break

Submission status: Wrong Answer

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(1,26):
        for b in range(1,26):
            s = encode(code,a,b)
            if 'that' in s:
                print(s)
                break
            elif 'this' in s:
                print(s)
                break

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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'or'this')in a:print(a);break

Submission status: Wrong Answer

Solution code:
for _ in[0]*int(input()):
 e=input()
 for i in range(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'or'this')in a:print(a);break

Submission status: Wrong Answer

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'or'this')in a:print(a);break

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
base = ord("a")

def restore(s):
  
  for a in [i for i in range(3, 26, 2) if i % 13]:
    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: Wrong Answer

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

M = 26
A = ord('a')
dic = {}
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 (a*x + b) % M
		
for a in re_prime:
	for b in range(M):
		n = ((F('t')*M + F('h'))*M + F('i'))*M + F('S')
		dic[n] = (a, b)
		n = ((F('t')*M + F('h'))*M + F('a'))*M + F('t')
		dic[n] = (a, b)

n = int(input())
for i in range(n):
	s = list(input().split())
	for x in s:
		if len(x) == 4:
			n = 0
			for c in x:	n = n*M + (ord(c)-A)
			if n in dic:
				a,b = dic[n]
				break
	tr = {}
	for i in range(M): tr[chr(A+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: Wrong Answer

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 = [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: Wrong Answer

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 dic
                print ''.join([dic.get(c, c) for c in s])
                break
        else:
            continue
        break

Submission status: Time Limit Exceeded

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')
    i = 3
    while True:
        x = affine(msg,[i,0])
        a = (c0-ord(x[0]))%26
        x = rot(x,a)
        if x in['this','that']: return [i,a]
        i += 2

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:
from itertools import product
n = int(input())
for _ in range(n):
    s = input()
    for alpha,beta in product([1,3,5,7,9,11,15,17,19,21,23,25],range(26)):
        g = "".join(chr((alpha*(ord(e)-ord("a"))+beta)%26+ord("a")) if not e == " " else " "  for e in s)
        if "that" in g or "this" in g: print(g); break

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from itertools import *
def code(a,b,st):
  v = ""
  for s in st:
    v += chr( ( a*(ord(s)-ord("a"))+ b ) % 26  + ord("a"))
  return v

def invert(string,codelist):
  for st in string:
    v = ""
    for s in st: v += codelist[s]
    print v,

def search(x,y,st):
  for e in st:
    if e == code(x,y,"that") or e == code(x,y,"this"):
      return { code(x,y,s):s for s in "abcdefghijklmnopqrstuvwxyz" }
  else: return False
      
n = int(raw_input())
for i in xrange(n):
  st = map(str, raw_input().split())
  for x,y in product(range(26),repeat=2):
    if x % 2 == 0 or x % 13 == 0: continue
    codelist = search(x,y,st)
    if codelist: break
  invert(st,codelist)
  print

Submission status: Accepted

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

Solution code:
def affine(x, a, b):
    result = []
    for i in range(len(x)):
        c = chr((a * (ord(x[i])-97) + b) % 26 + 97)
        result.append(c)

    return ''.join(result)


def decode_key(a, b):
    key = "abcdefghijklmnopqrstuvwxyz"
    result = []
    for i in range(len(key)):
        result.append(affine(key[i], a, b))
    return ''.join(result)


a = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
n = int(input())
for i in range(n):
    ai = 0
    b = 0
    line = input()
    words = line.split()
    for i in range(26):
        for j in range(len(a)):
            if affine('that', a[j], i) in words:
                ai = j
                b = i
            if affine('this', a[j], i) in words:
                ai = j
                b = i
        if ai and b:
            break

    line = line.translate(str.maketrans(decode_key(a[ai], b), "abcdefghijklmnopqrstuvwxyz"))
    print(line)

Submission status: Accepted

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
#start = time.clock()

n=int(raw_input())
for h in range(n):
    tmp=raw_input()
    for a in range(26):
        if gcd(a,26)!=1:
            continue
        for b in range(26):
            s=''
            for q in tmp:
                if q.isalpha():
                    s+=chr((((ord(q)-97)*a+b)%26)+97)
                else:
                    s+=q
            if 'that' in s or 'this' in s:
                print s

Submission status: Accepted

Solution code:
from math import *
PI = 3.1415926535898
x = "this"
z = "that"
def f(c, n, d):
	k = ((ord(c) - ord('a')) * n + d ) % 26
	return chr(ord('a') + k)
while True:
    try:
    	n = input()
    	for i in range(n):
	        s = str(raw_input())
	        res = ""
	        ans = ""
	        for i in range(26):
	        	for j in range(26):
		            res = ""
		            for a in s:
		                if a.isalpha():
		                    res += f(a, i, j)
		                else:
		                    res += a
		            if res.find(x) >= 0 or res.find(z) >= 0:
		                ans = res
	        print ans
    except EOFError:
        break

Submission status: Accepted

Solution code:
from string import ascii_lowercase


def ex_gcd(a, b, y0=0, y1=1):
    s, r = a // b, a % b
    return ex_gcd(b, r, y1, y0 - s * y1) if r else y1


def decrypt(c, a_rev, b):
    return chr(a_rev * (ord(c) - 97 - b) % 26 + 97) if c in ascii_lowercase else c


decrypt_that = {}
decrypt_this = {}

for a in (1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25):
    for b in range(26):
        _t, _h, _a, _i, _s = map(lambda c: chr((a * c + b) % 26 + 97), (19, 7, 0, 8, 18))
        decrypt_that[''.join((_t, _h, _a, _t))] = (a, b)
        decrypt_this[''.join((_t, _h, _i, _s))] = (a, b)

n = int(input())
while n:
    line = input()
    word4 = {w for w in line.split() if len(w) == 4}
    a, b = 0, 0
    for word in word4:
        if word in decrypt_that:
            a, b = decrypt_that[word]
            break
        if word in decrypt_this:
            a, b = decrypt_this[word]
            break
    a_rev = ex_gcd(26, a)
    print(''.join(decrypt(c, a_rev, b) for c in line))

    n -= 1

Submission status: Accepted

Solution code:
def gcd(a,b): return a if b == 0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)

for h in range(input()):
	tmp = raw_input()
	for a in range(26):
		if gcd(a,26)!=1:
			continue
		for b in range(26):
			s = ""
			for q in tmp:
				if q.isalpha():
					s += chr((((ord(q)-97)*a+b)%26)+97)
				else:
					s += q
			if ("that" in s)or("this" in s):
				print s

Submission status: Accepted

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

def is_this(word, a, b):
    if trans(word, a, b) == "this":
        return True
    return False

def is_that(word, a, b):
    if trans(word, a, b) == "that":
        return True
    return False

def trans(word, a, b):
    tra = ''
    for i in range(len(word)):
        tra += chr(97+(a*dic[word[i]]+b)%26)
    return tra

dic = {}
for i in range(26):
    dic[chr(97+i)] = i
n = int(raw_input())
for i in range(n):
    text = map(str, raw_input().split())
    j = 0
    flag = True
    while flag:
        if len(text[j]) == 4:
            tmp = text[j]
            for alfa in range(100):
                if alfa % 2 == 0 or alfa % 13 == 0:
                    continue
                for beta in range(26):
                    if is_this(tmp, alfa, beta) or is_that(tmp, alfa, beta):
                        flag = False
                        break
                if not flag:
                    break
        j += 1
    ans = []
    for t in text:
        ans.append(trans(t, alfa, beta))
    print " ".join(map(str, ans))

Submission status: Accepted

Solution code:
def affine(word, alpha, beta):
    word = list(word)
    for i in range(len(word)):
        word[i] = albs[(albs.index(word[i]) * alpha + beta) % 26]
    return ''.join(word)
albs = 'abcdefghijklmnopqrstuvwxyz'
alphas = [1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25]
betas = list(range(26))
for _ in range(int(input())):
    words = input().split(' ')
    for alpha in range(26):
        for beta in range(26):
            test = list(map(lambda x: affine(x, alpha, beta), words))
            if 'that' in test or 'this' in test:
                print(*test)
                break
        else:
            continue
        break

Submission status: Accepted

Solution code:
n = int(input())
s = "abcdefghijklmnopqrstuvwxyz"
for i in range(n):
  sent = input().rstrip()
  l = [i for i in sent]
  c = 0
  for a in range(26):
    for b in range(26):
      l2 = []
      for i in range(len(l)):
        if l[i] in s:
          l2.append(s[(s.index(l[i])*a+b)%26])
        else:
          l2.append(l[i])
      sent2 = "".join(l2)
      if ("that" in sent2) or ("this" in sent2):
        print(sent2)