AOJ 1250: Leaky Cryptography

問題

Leaky Cryptography | Aizu Online Judge

解法

Kの後ろからi桁目を0にした時に、下i桁の答えが条件に合うならば、Kの後ろからi桁目は0であり、合わなければ1である。

コード

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int S = sc.nextInt();
        for (int j = 0; j < S; ++j) {
            long[] input = new long[9];
            for (int i = 0; i < 9; ++i) {
                // 10進数に変換しておく
                input[i] = Long.parseLong(sc.next(), 16);
            }

            long key = 0;
            for (int i = 0; i < 32; ++i) {
                long sum = 0;
                for (int q = 0; q < 8; ++q) {
                    sum += input[q] ^ key;
                }

                if ((sum & (1L << (i + 1) - 1)) != ((input[8] ^ key) & (1L << (i + 1) - 1))) {
                    // keyの後ろからi桁目を0として計算した時に、sumとinput[8]の下i桁が等しくならなかった場合、
                    // keyのi桁目を1にする
                    key |= (1L << i);
                }
            }
            System.out.println(Long.toString(key, 16).toLowerCase());
        }

        sc.close();
    }
}