AOJ 1250 : Leaky Cryptography
問題リンク:Leaky Cryptography | Aizu Online Judge
問題概要:
(N1^K) + (N2^K) + ・・・ + (N8^K) = (N9^K) となるKを見つけろ
ここで、N1,...,N9,Kは32bit integerで16進数
解法:
最下位ビットから決定していった
各Nの各桁についてKの同じ桁を0からfまで決めてあげて式をみたすかどうかを判定した
入力も16進数であたえられる
これはC++では cin >> hex >> N[i]; という様に hex をはさんでやれば16進数の入力を10進数としてとってくれる
10進数を16進数のstringに変換する時も、stringstream に入れる際に,
stringstream ss;
ss << hex << value;
といった感じで hex を間にはさめばよい
コード:
typedef long long ll; ll N[9]; string lltos(ll x) { stringstream ss; ss << hex << x; return ss.str(); } void rec(int p,string K,ll carry) { if(p >= 8) { reverse(K.begin(),K.end()); int cnt = 0; rep(i,K.size()) { cnt++; if(K[i] == '0')continue; K = K.substr(i,K.size()-i); break; } if(cnt == K.size())K = "0"; cout<< K << endl; return; } ll cret[9]; ll x = 0xf*pow(16LL,p); ll v = pow(16LL,p); rep(i,9)cret[i] = (x&N[i])/v; rep(k,16) { ll total = carry; rep(i,8) { total += (cret[i]^k); } if(total%16 == (cret[8]^k)) { rec(p+1,K+lltos(k),total/16); } } } int main() { int T; cin >> T; while(T-- > 0) { rep(i,9)cin >> hex >> N[i]; rec(0,"",0); } return 0; }