AOJ0040

問題:Affine Cipher
アフィン暗号で暗号化された文字列を復号する問題．
F(γ) = (α・γ＋β) mod 26
文字列の各文字はこの式に基づいて暗号化されている．αとβは分からない．
ただし，元の文字列には必ず"this"か"that"が入っているのでここからαとβを求め，文字列を復号する．

方針は，考えられるすべてのα，βのパターンで"this"と"that"をアフィン暗号化してテーブルを作っておく．
入力された文字列とテーブルからα，βを特定し，元の文字列に戻す．
上式の逆関数を求めるのではなく，これもテーブル化すると楽．
map便利ィ!!

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <map>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

char F(int a,int b,char y){
	y = y-'a';
	return (a*y + b)%26 + 'a';
}
int main(){
	string s1,s2;
	map<string,pair<int,int> > table;
	s1 = "this";
	s2 = "that";
	int a,b;
	for(a=0;a<26;++a)for(b=0;b<26;++b){
		if(a%13==0 || a%2==0)continue;
		string s1_,s2_;
		for(int i=0;i<4;++i)s1_ += F(a,b,s1[i]);
		for(int i=0;i<4;++i)s2_ += F(a,b,s2[i]);
		table[s1_] = pair<int,int>(a,b);
		table[s2_] = pair<int,int>(a,b);
	}
	int n;
	cin >> n;
	string tmp;
	getline(cin,tmp);
	for(int l=0;l<n;++l){
		map<char,char> trans;
		string s;
		stringstream ss;
		vector<string> vs,vst;
		int a,b;
		getline(cin,s);
		ss << s;
		while(ss >> s){
			if(s.length() == 4)
				vs.push_back(s);
			vst.push_back(s);
		}
		rep(i,vs.size()){
			if ( table.find( vs[i] ) != table.end() ){
				a = table[vs[i]].first;
				b = table[vs[i]].second;
				break;
			}
		}
		rep(i,26){
			trans[ F(a,b,i+'a') ] = i+'a';
		}
		rep(i,vst.size()){
			rep(j,vst[i].size()){
				cout << trans[vst[i][j]];
			}
			if(i==vst.size()-1)cout << endl;
			else cout << " ";
		}
	}
	return 0;
}