読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

AOJ 1250 : Leaky Cryptography

AOJ 16進数

問題リンク: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;
}